Path Finding
Posted: 25 Feb 2010, 10:04
I searched the forums a good amount. I found a few topics and post scattered about on the topic. Also, of course the fact that the engine already performs decent (not perfect) path finding. But, as I can tell myself and from the forums the engine does not provide the features, configuration, or control needed/wanted for writing a AI.
My intentions were to share with you some methods that I have come to know and use commonly over the years and in return find out the methods that some of you use. I know that the terminology and theory can be confusing, but as I understand and have experienced the actual application can be exponentially easier than it appears.
When I first had contact with path finding it was trivial and then later I encountered the traveling salesman problems which really kept me busy for a few months searching for not only solutions for understanding of the problems.
I had come to find out a few major concepts which I hope can be informative and helpful to you in return for some replies that can benefit me now and later in my works. I normally keep to myself and refrain from openly discussing such things but I feel that it would be quite helpful to everyone.
The problem can be represented in many forms, but it is always the same concept. You have a starting and ending point. Then you have between these points a lot of different possibilities. The between is usually referred to as a graph, network, tree, or nodes. From visually similar to a line, tree, or on the far opposite something that looks like a tangled mess of lines and dots.
To stay simple. A grid or bitmap. Like, the slope map in the game engine is essentially exactly the same as a graph. Each point connections to one or more points. With the game each unit has a maximum slope it can travel on. There are about 8 to 12 unique slope values for all the units (in the BA mod at least). This means that there exists that many individual maps which represent passable or impassable point. Where passable means the unit can move at this point in the map. To keep it simple we will consider a single map for a single maximum slope value.
There are likely hundreds of unique ways to solve this single maximum slope map, but they are all essentially based around only a few algorithms. The first algorithm is:
Heading In The One Direction
This is, in my opinion, likely the first method anyone thinks about. You figure you just start moving in the direction towards the destination and eventually you will arrive, and in a lot of situations this will be successful but the problems lies when not only objects are in the path but curved objects that are cup shaped which can trap you and not allow you to slide 90 degree to the left or right of your direction vector.
The Exhaustive Search
It does not matter if you have a network or node or a bitmap/grid. The concept is exactly the same. You create a list/array/table. And you place a item which you starting location position. This is normally a coordinate ([xy] or [xyz]) or a pointer to the starting node. Then you enter into a outer loop and then a inner loop. And, inside the inner loop you simply take each item in the list and spawn a new item for each direction you can move from the current position of the item. Then you delete the current item. And, by doing this continually you will eventually search the entire graph (using this words instead of network of nodes) or bitmap. The variations are working from the items in the list:
[1] that have the fewest moves
[2] that are closer to the destination
And, likely some other variations but those are the common. If you are considered the speed factor then as each item is created a time parameter is incremented depending on the node or grid unit it has been just left or just jumped to. And, you might pick the nodes with the lowest time first instead of lowest moves.
The problem is this algorithm can not only eat CPU like candy, but it can eat memory too. Since the more nodes or bigger the grid the worse it gets. This is in my opinion the second method most people try. It usually stems from the fact that you get so annoyed over such a simple problem that you get mad and resort to just doing it old fashioned brute force way (which does occasionally work quite well).
Random Movements
Since all grid/bitmaps can be converted into a graph we can consider them one in the same. For some problems the complexity of doing an exhaustive search is so time consuming that believe it or not just simple making random paths can prove very effective. You just keep doing it and for each better path you find you replace the original path. There are many variations to this problem which are highly related to the actual factors in the graph. Where you may weight previous paths by values which caused the random decisions to be biased by a certain amount. There is decay of weighting and many other more complex methods.
Hybrid Methods
You even have methods that use random path generation, exhaustive searches, and straight line travel all in the same algorithm. In some cases you may use one before the other in a certain order or at different times. There is even algorithms which produce rough paths using one algorithm and then use another algorithm to refine this path over time or all at one.
Compile-Time/Load-Time/Run-Time/Cache
All the methods I talked about above use run-time computations. But, there are situations where you can perform computations one time before your algorithm ever runs, or right before it runs, or save computations during run-time for usage later. All of this methods speed the computation up. Caching I have seen used a lot to store already computed solutions so the computation never has to be done before. Or, compile-time computations where a complex graph may be turned into a simple one that overlays the complex one so the run-time algorithm does not have as many possibilities.
--
Some of the best algorithms use a combination. From what I have understood a lot is that you generally want to use the appropriate tool for the job. So doing a exhaustive search over a 1000x1000 grid is normally not the best tool. But, breaking the problem down such as:
Compile/Load Time Rough Graph With Exhaustive Search
Where during compile or load time you pre-compute a rough network of nodes that is far simpler than the original graph. In essence you break the original problem down into a list of smaller problems where you can apply exhaustive searching algorithms. The problem is normally that the resolution of the pre-computed graph will affect how close you get to the optimal solution. The higher the graph resolution the closer you get to just being better off doing a pure exhaustive search. The lower resolution you get the further you get from the optimal solution but it might be so bad it is not even worth using. Also, being able to dynamically adjust the graph for certain parts can help. But, talking about all the possible variations would lead to hundreds of pages of text which is not what I am trying to do.
Regions, Zones, And Portals
For my few years I have found a interesting solution. And one that when applied to the path finding in the Spring engine for AI usage seems to have really good potential.
What you do is:
Convert Slope Map Into Passable Map
You take the slope max and define your max slope. Then produce a second map where zeros represent passable points and ones represent unpassable points (this is not a bit(computer bit)map -- a grid).
Find Regions
A region is a area like a island. Some maps have zero regions. Others have one region, and some can have 80 to 100 regions. A region is a area on the map where any point in the region can be reached from any other point in the region. But, you can not travel between regions. This is caused by the terrain between two regions being impassable or too much slope or underwater. You can define regions by representing them with a unique value such as one or higher for each region.
Replace the zero values in the map/grid/bitmap with a unique value for that region which you can use to find the zones below.
Find Zones
Now that you have you one or multiple regions you are still back at square one like we started. You have a grid (graph) with maybe 10^25 different solutions and only a handful are optimal. So you read everything I wrote and got nowhere, haha!
Each region has one or more zones. To define a zone at least in my case I use a convex polygon. I know hardly any geometry or trigonometry. But, a convex polygon in this case is important because you can start from any point on any side of the polygon (where are speaking about on the inside of it) and travel in a straight line to the other point with out crossing a line. This is important. We need as much straight line travel as we can get because it is computationally cheap.
The hard part is breaking a region which is really just a potentially large and complex concave polygon into many smaller convex polygons. But, this is another problem with multiple solutions and only a handful are close to optimal. You can break it down in many ways. There a lots of algorithms on the internet to do so.
One method I have found which works really fast which is contrary to what most people think when they first think about doing it -- is to use a scan line to produce the convex polgyons. A scan line? Yeah. You pretend to hold a ruler and slowly move it in one direction over the entire region. As the ruler passes over the insides of the polygon it produces segments. These segments can be stacked onto previous segments to build polygons. As you reach a point where one segment stacks onto two existing polygons you simply create another polygon and start it there. Or, when a single polygon (being created from the scan line) reaches a point where it splits (you have multiple segments that stack on the polygon) you simply create multiple new polygons.
After one pass of the scan line the region will be turned into some decent looking smaller polygons. But, most are still concave. You do another pass left to right (instead of top to bottom) over the polygons you just produces and you get more the same polygons or more. But, you will notice that some of the concave polygons are now convex. So do it again from the diagonal direction of 45 degree and then a forth time from the direction of -45 (negative forty-five degrees). Now, you have a bunch of convex polygons representing the region.
Find Portals
A portal is where two zones (remember our zones are convex polygons) touch on their sides. This creates a line called a portal. A zone could have multiple portals on a single side of it's polygon shape. Once you determine all the portals you have now created a graph again.
Portal Graph
Using the portal graph is actually exactly like the rough graph approached I talked about a while back. Exactly, this rough graph was created in a dynamic way. Large open areas are represented by large convex polygons instead of two or more nodes. The zones are adjusted to the complexity of the map at different points. The improvement is in how the convex polygons are created from the concave ones. The less polygons you create to get all convex the smaller the graph.
Each zone can have a distance associated which represents the distance between the two vertex that are the furthest away. Using this value you can quickly eliminate many zones when trying to determine what zone you are current in. Also other algorithms can be used to further reduce the time needed to search the list of regions then zones.
Once you find your zone the graph is for most maps using the Spring Engine very small. For some of the largest maps you might get 6000 zones (nodes) which if doing a exhaustive search is the equivalent of a 77x77 unit map. I consider this not bad.
Also using pre-computation you can split the map in half, thirds, or smaller by finding choke points and doing some dynamic weighting and caching for you search routines when trying to path to the other side of these choke points.
I have implemented the entire above algorithm in nothing but Lua, and to what would be expected it runs very fast. I think one of the largest maps I have took less than 10 seconds of computation. I can not say for sure because I just added rotations so I can chop my polygons in the diagonal direction. But, a single pass is very fast. I think it was less than a second. I also use an exhaustive brute force searching to find the regions. I go through each unit of the grid and start spreading until I reach the boundaries of that region. A bad side is that I will currently produce a region/zone graph for each unique maximum slope. But, keep in mind that I have a DLL written in C where I can simply translate into if I need more speed. And, also that unless the map becomes greatly deformed that brute force searching and simple zone limited re-computations are possible.
I am wondering what methods some of you have used, and I hope that some people out there have been able to take some of the stuff that took me years to learn and do it in less time so that you can help me now or later. Because, helping each other does not make anyone more or less but rather advanced us all forward as a group and not backwards.
[edit]I have not even though to look at how the Spring Engine does path finding. Maybe someone can give a good easy to understand overview of it if they know. It may have a better way.[/edit]
My intentions were to share with you some methods that I have come to know and use commonly over the years and in return find out the methods that some of you use. I know that the terminology and theory can be confusing, but as I understand and have experienced the actual application can be exponentially easier than it appears.
When I first had contact with path finding it was trivial and then later I encountered the traveling salesman problems which really kept me busy for a few months searching for not only solutions for understanding of the problems.
I had come to find out a few major concepts which I hope can be informative and helpful to you in return for some replies that can benefit me now and later in my works. I normally keep to myself and refrain from openly discussing such things but I feel that it would be quite helpful to everyone.
The problem can be represented in many forms, but it is always the same concept. You have a starting and ending point. Then you have between these points a lot of different possibilities. The between is usually referred to as a graph, network, tree, or nodes. From visually similar to a line, tree, or on the far opposite something that looks like a tangled mess of lines and dots.
To stay simple. A grid or bitmap. Like, the slope map in the game engine is essentially exactly the same as a graph. Each point connections to one or more points. With the game each unit has a maximum slope it can travel on. There are about 8 to 12 unique slope values for all the units (in the BA mod at least). This means that there exists that many individual maps which represent passable or impassable point. Where passable means the unit can move at this point in the map. To keep it simple we will consider a single map for a single maximum slope value.
There are likely hundreds of unique ways to solve this single maximum slope map, but they are all essentially based around only a few algorithms. The first algorithm is:
Heading In The One Direction
This is, in my opinion, likely the first method anyone thinks about. You figure you just start moving in the direction towards the destination and eventually you will arrive, and in a lot of situations this will be successful but the problems lies when not only objects are in the path but curved objects that are cup shaped which can trap you and not allow you to slide 90 degree to the left or right of your direction vector.
The Exhaustive Search
It does not matter if you have a network or node or a bitmap/grid. The concept is exactly the same. You create a list/array/table. And you place a item which you starting location position. This is normally a coordinate ([xy] or [xyz]) or a pointer to the starting node. Then you enter into a outer loop and then a inner loop. And, inside the inner loop you simply take each item in the list and spawn a new item for each direction you can move from the current position of the item. Then you delete the current item. And, by doing this continually you will eventually search the entire graph (using this words instead of network of nodes) or bitmap. The variations are working from the items in the list:
[1] that have the fewest moves
[2] that are closer to the destination
And, likely some other variations but those are the common. If you are considered the speed factor then as each item is created a time parameter is incremented depending on the node or grid unit it has been just left or just jumped to. And, you might pick the nodes with the lowest time first instead of lowest moves.
The problem is this algorithm can not only eat CPU like candy, but it can eat memory too. Since the more nodes or bigger the grid the worse it gets. This is in my opinion the second method most people try. It usually stems from the fact that you get so annoyed over such a simple problem that you get mad and resort to just doing it old fashioned brute force way (which does occasionally work quite well).
Random Movements
Since all grid/bitmaps can be converted into a graph we can consider them one in the same. For some problems the complexity of doing an exhaustive search is so time consuming that believe it or not just simple making random paths can prove very effective. You just keep doing it and for each better path you find you replace the original path. There are many variations to this problem which are highly related to the actual factors in the graph. Where you may weight previous paths by values which caused the random decisions to be biased by a certain amount. There is decay of weighting and many other more complex methods.
Hybrid Methods
You even have methods that use random path generation, exhaustive searches, and straight line travel all in the same algorithm. In some cases you may use one before the other in a certain order or at different times. There is even algorithms which produce rough paths using one algorithm and then use another algorithm to refine this path over time or all at one.
Compile-Time/Load-Time/Run-Time/Cache
All the methods I talked about above use run-time computations. But, there are situations where you can perform computations one time before your algorithm ever runs, or right before it runs, or save computations during run-time for usage later. All of this methods speed the computation up. Caching I have seen used a lot to store already computed solutions so the computation never has to be done before. Or, compile-time computations where a complex graph may be turned into a simple one that overlays the complex one so the run-time algorithm does not have as many possibilities.
--
Some of the best algorithms use a combination. From what I have understood a lot is that you generally want to use the appropriate tool for the job. So doing a exhaustive search over a 1000x1000 grid is normally not the best tool. But, breaking the problem down such as:
Compile/Load Time Rough Graph With Exhaustive Search
Where during compile or load time you pre-compute a rough network of nodes that is far simpler than the original graph. In essence you break the original problem down into a list of smaller problems where you can apply exhaustive searching algorithms. The problem is normally that the resolution of the pre-computed graph will affect how close you get to the optimal solution. The higher the graph resolution the closer you get to just being better off doing a pure exhaustive search. The lower resolution you get the further you get from the optimal solution but it might be so bad it is not even worth using. Also, being able to dynamically adjust the graph for certain parts can help. But, talking about all the possible variations would lead to hundreds of pages of text which is not what I am trying to do.
Regions, Zones, And Portals
For my few years I have found a interesting solution. And one that when applied to the path finding in the Spring engine for AI usage seems to have really good potential.
What you do is:
Convert Slope Map Into Passable Map
You take the slope max and define your max slope. Then produce a second map where zeros represent passable points and ones represent unpassable points (this is not a bit(computer bit)map -- a grid).
Find Regions
A region is a area like a island. Some maps have zero regions. Others have one region, and some can have 80 to 100 regions. A region is a area on the map where any point in the region can be reached from any other point in the region. But, you can not travel between regions. This is caused by the terrain between two regions being impassable or too much slope or underwater. You can define regions by representing them with a unique value such as one or higher for each region.
Replace the zero values in the map/grid/bitmap with a unique value for that region which you can use to find the zones below.
Find Zones
Now that you have you one or multiple regions you are still back at square one like we started. You have a grid (graph) with maybe 10^25 different solutions and only a handful are optimal. So you read everything I wrote and got nowhere, haha!
Each region has one or more zones. To define a zone at least in my case I use a convex polygon. I know hardly any geometry or trigonometry. But, a convex polygon in this case is important because you can start from any point on any side of the polygon (where are speaking about on the inside of it) and travel in a straight line to the other point with out crossing a line. This is important. We need as much straight line travel as we can get because it is computationally cheap.
The hard part is breaking a region which is really just a potentially large and complex concave polygon into many smaller convex polygons. But, this is another problem with multiple solutions and only a handful are close to optimal. You can break it down in many ways. There a lots of algorithms on the internet to do so.
One method I have found which works really fast which is contrary to what most people think when they first think about doing it -- is to use a scan line to produce the convex polgyons. A scan line? Yeah. You pretend to hold a ruler and slowly move it in one direction over the entire region. As the ruler passes over the insides of the polygon it produces segments. These segments can be stacked onto previous segments to build polygons. As you reach a point where one segment stacks onto two existing polygons you simply create another polygon and start it there. Or, when a single polygon (being created from the scan line) reaches a point where it splits (you have multiple segments that stack on the polygon) you simply create multiple new polygons.
After one pass of the scan line the region will be turned into some decent looking smaller polygons. But, most are still concave. You do another pass left to right (instead of top to bottom) over the polygons you just produces and you get more the same polygons or more. But, you will notice that some of the concave polygons are now convex. So do it again from the diagonal direction of 45 degree and then a forth time from the direction of -45 (negative forty-five degrees). Now, you have a bunch of convex polygons representing the region.
Find Portals
A portal is where two zones (remember our zones are convex polygons) touch on their sides. This creates a line called a portal. A zone could have multiple portals on a single side of it's polygon shape. Once you determine all the portals you have now created a graph again.
Portal Graph
Using the portal graph is actually exactly like the rough graph approached I talked about a while back. Exactly, this rough graph was created in a dynamic way. Large open areas are represented by large convex polygons instead of two or more nodes. The zones are adjusted to the complexity of the map at different points. The improvement is in how the convex polygons are created from the concave ones. The less polygons you create to get all convex the smaller the graph.
Each zone can have a distance associated which represents the distance between the two vertex that are the furthest away. Using this value you can quickly eliminate many zones when trying to determine what zone you are current in. Also other algorithms can be used to further reduce the time needed to search the list of regions then zones.
Once you find your zone the graph is for most maps using the Spring Engine very small. For some of the largest maps you might get 6000 zones (nodes) which if doing a exhaustive search is the equivalent of a 77x77 unit map. I consider this not bad.
Also using pre-computation you can split the map in half, thirds, or smaller by finding choke points and doing some dynamic weighting and caching for you search routines when trying to path to the other side of these choke points.
I have implemented the entire above algorithm in nothing but Lua, and to what would be expected it runs very fast. I think one of the largest maps I have took less than 10 seconds of computation. I can not say for sure because I just added rotations so I can chop my polygons in the diagonal direction. But, a single pass is very fast. I think it was less than a second. I also use an exhaustive brute force searching to find the regions. I go through each unit of the grid and start spreading until I reach the boundaries of that region. A bad side is that I will currently produce a region/zone graph for each unique maximum slope. But, keep in mind that I have a DLL written in C where I can simply translate into if I need more speed. And, also that unless the map becomes greatly deformed that brute force searching and simple zone limited re-computations are possible.
I am wondering what methods some of you have used, and I hope that some people out there have been able to take some of the stuff that took me years to learn and do it in less time so that you can help me now or later. Because, helping each other does not make anyone more or less but rather advanced us all forward as a group and not backwards.
[edit]I have not even though to look at how the Spring Engine does path finding. Maybe someone can give a good easy to understand overview of it if they know. It may have a better way.[/edit]
