Path Finding

[kmcguire]

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]

[kmcguire]

Oh, and of some limited help to other people. I wrote a DLL which uses Lua 5.1 statically linked. There were two reasons. The first being I did not like that I would have to include the AI into the mod files and could not distribute it separately and so that I could translate into C if I needed a boost to performance and memory consumption. But, here is the link. I just a hour or so ago started refining the path finding code in skitzo.lua to incorporation a function for rotating the bitmap so it will have syntax errors, but it is only a little bit away from having the path finding working for those who might be interested in a more complete example. Or, even a base to build a individually distributed AI written in Lua using the DLL loading mechanism.

My interaction with the game engine is done almost entirely in Lua using some generic functions to pack data and call certain engine functions with standard return, type, and number of arguments. Even extracts the interface functions from the C header file.

http://www.kmcguire.org/McGuireAI.kgb

Have fun maybe. =)

[hoijui]

wow...
thanks!
i have never done path finding so far, and .. sure can not give tips
just.. when reading your text, i kind of lost track at the point with the scan lines, where you scan with the 4 different angles. i would have needed some paint sketches there, but it makes no sense to create them for me, as i do not plan to implement a path finder.

all i know about springs path finder is, that it pre-calculates and caches a rough set of paths ("looking for the way on a 1:100 map"), and calculates detailed paths at runtime ("where to put my feet next").

if you have a well performing, generically usable algorithm, the best for spring would be, if it was implemented inside the engine, and made available through Lua and the C AI interface. optimally, it could even replace the engines own path finder of course :D though.. i really do not know enough about the requirements for that.

[Kloot]

...
Convert Slope Map Into Passable Map
...
Find Regions
...

This algorithm is called flood-fill. The (unfinished) XAI pathfinder uses it, but generating a map of passable regions for every movetype is already too slow for typically-sized slope- and heightmaps. Turning those into convex polygons is an interesting extension though (one that gets you into navigation-mesh territory).

[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.

Spring's PF is based on hierarchical (multiple-resolution) A*, with a "rough graph" precomputation stage.

[ivand]

kmcguire:

Great post and explanation! I did something similar, but used tessellation with rectangles (one big in the center, smaller ones on the rugged edges around big one) to represent a region. Unfortunately I was lazy and never finished it.

I see you've studied lots of stuff so, I just wanted to ask what is your opinion about HPA*(http://aigamedev.com/open/reviews/near- ... thfinding/) and this (http://games.cs.ualberta.ca/~nathanst/p ... ide_dm.pdf).


Thanks in advance.

//Ivan

[kmcguire]

Near-Optimal Hierarchical Path Finding
Yes, this seems to essentially be what I am doing. But, I am so happy that you have posted this. As the information will help to keep me steered in the right direction.

<quote>"the initial search problem has been decomposed into several very small searches (one for each cluster on the abstract path), with low complexity."</quote>
Like your algorithm, mine, and this one. We broke our larger problem into smaller pieces. Or, took a high resolution problem and looked for a low resolution initial solution. I suppose that the Spring Engine is also doing the same. The only problem here is that if you the low resolution (or abstract) representation happens to lose some key information. In some a individual case the Spring engine missed a opening in a wall on a map. So, when I first started this thread I have assumed that the engine's low resolution (rough graphs) are losing key information in tight, small, enclosed areas of the map. However, the concept is still highly valid. I am so happy you have posted this, Kloot, and hoijui have essentially confirmed.

I see that you used squares. I am now envy as I am not sure if these squares may be a better approach then convex polygons. I suppose it completely depends on the number of polygons. Oh, and when I say polygon I mean anything with 3 or more sides. Now, if someone reads this thread they can consider a object shape too when breaking the map up into smaller maps.

<quote>"To improve the solution quality (i.e., length and aesthetics), we perform a post processing phase for path smoothing. Our technique for path smoothing is simple, but produces good results"</quote>

I like this. This is what I was struggling with for a day or so. I could get the abstract path, but needed to perform the smoothing with out eating CPU. I have figured out that I can create what I call a bounding polygon for each square/polygon/zone/sub-area. Like the paper my zones have portals which are simply sides that connect one zone to another. The problem is that there is no easy solution. The possible solutions are the units in length of each side (that is a portal) multiplied by the other. Solutions=SideALength*SideBLength. So I have decided to generate a bounding polygon which represents going from SideAPointA to SideBPointB, and SideAPointB to SideBPointB.

I upload picture with bounding polygons (red lines) inside actual zones. And, each side of the portal is connected to the adjacent. Once done with each portal for each portal in a zone you can get a minimum and maximum travel time through the zones. So the abstract graph can also include travel times which is interesting.

Anyway this is where I have left off from. I found out that cutting the map 4 times is not a good idea. But, a second cut may be well for breaking the zones, squares, polygons down further in convex polygons. Maybe it was my algorithm (and being in Lua), but it took way too long for large maps.

<quote>The hierarchy can be extended to several levels, transforming the abstract graph into a multi-level graph. In a multi level graph, nodes and edges have labels showing their level in the abstraction hierarchy. We perform path-nding using a combination of small searches in the graph at various abstraction levels. Additional levels in the hierarchy can reduce the search effort, especially for large mazes.</quote>

Yes, this is what I am having to do now. Noted, that Lua can be magnitudes slower than C. I am still having a slow down. I have split the map into regions and zones. But, I may have like 1200 zones. So I too am having to partition, split, or break my graph into larger pieces.

Which, in my opinion, is the same as building multi-layers of resolution or a hierarchy essentially. But, this paper you have presented has sort of solidified my ideas. Where I was unsure I have now become more sure. So thanks for showing this paper to me.

<quote>The way we build the abstract graph ensures that we always nd the same solution, no matter how many abstract levels we use. In particular, adding a new level l > 2 to the graph does not diminish the solution quality.</quote>

And, yes here too. They also confirm. That however the graph is simplified for faster rough path calculation. You should not comprise the quality of the solutions. I felt like when playing on that map with the Spring Engine it somehow comprised the quality of it's paths. When my units went around the long way only because the short way was kind of narrow. But, maybe this was caused by some other unknown factor. Never the less. Building higher level representations which do not lose key elements in the lower level representations is a must. If my high level graph causes me to miss one out of four paths. Then I lost key information, and made part of my low level graph useless.

What is really interesting here. Is that we are not somehow using magic to do less computation. Instead, we are delaying computation until a later time. I just recently actually focused on this completely. I was folding my zone graph into parts. At first I was super excited that I had somehow reduced the computations. But, what I had done was really just delay the computation by enabling myself to only compute a part of the graph search, and then continue at a later point.

I had found choke points in my graph. Points that you have to pass through to get to the other side. So before I did my abstract path I considered if the destination was on the other side of this fold. If it was then I checked cache for a path to the fold, if so I used it, then I checked cache for a path from the fold to the destination, and if so I used it. But, interesting was the properties that:

[*] I doubled my cache resolution. Lots of paths were now two cache entries instead of one because the cache entries can be split if the graph is split.
[*] Allows the delayed computation of the last part of the path if possible.

I suppose this was sort of like having an higher level graph with only two nodes. The split of the lower graph produces the two sides (two nodes). Now that I have read this paper you have posted I will surely further investigate breaking the graph into more pieces and **trying** to produce more of a hierarchy.

Direction Map For Cooperative Path Finding
Ah, this is also a very excellent resource. I have never worked with path finding for a RTS. Which, I have lately discovered needs corporative path finding for all the little units to not constantly run into each other. I can not comment much on this. I can say that when I do explore this (days from now) or years this direction map seems like a very good start. I was doing some quick thinking in my head and I see where it has potential. But, I am no expert by any means.

Squares Instead Of Polygons
I am really going to have to look and see if using squares would be better, since it disturbed me that I could be losing out here using them. Thank you very much for this idea to investigate.

[ivand]

kmcguire:
I haven't read all your previous post thoughtfully yet. Will do it a little later.

What I did wasn't exactly hierarchical map representation, at least the algorithm I used wasn't able to create multilevel hierarchy (like HPA*).
The following briefly describes steps I used to build tesselated map representation. It's being given just for information.

1. We have slope map. Lets convert it into pass map for each movetype. Now we have the array with pass cost (if one can pass) and impassable values.
2a. Next I used the procedure to split rectangle (first rectangle is the map by itself) into 4 rectangles. For instance If I have original rectangle with coordinates (0,0)-(2*W,2*H) then the procedure will return 4 rects: (0,0)-(W,H);(W,0)-(2*W,H);(0,H)-(W,2*H);(W,H)-(2*W,2*H).
2b. After that all four rects are inspected if they are "homogenous". Homogenous rectangle is the rectangle which has all passable or all impassible points. if the rect is homogenous then store it and mark pass-ability property, if it's not then repeat split procedure (2a) on the non-homogenous rectangle.
3. As a result of 2 we have lots of rects with pass-ability property set. And now we have to merge neighbor rects into bigger ones. Indeed merge should be done with respect to pass-ablity. The merge is done in do-while loop and being stoped if no new merge is available. the core merge algorithm is to check if two rects have the common edge and edges of two of rects have the same start and end coordinates.
4. After merge is done we have more or less big rects and still plenty of smaller rects which covers rough regions. After that all information is converted into the node-edge notation. There node is the center of the rectangle, and the edge is euclidean distance (one can use different metric indeed) to neighbor rect.
5. Next I used Floyd Warshall or Johnson algorithm to create and cache all-pairs-SPT.
6. For further optimization (x,y)-->RectID index could be created.
7. Now theoretically for every (S,G) pairs we can match (RectID1,RectID2) pair. This pair is used to get a metric from AllPair-SPT cache (which is really fast). And after that ordinal A* could be used with heuristic got from rect-to-rect directions.

As I told I was lazy and did only 6 steps from the preceding description.

[joshthewhistler]

I have read the previous posts and wondered whether the danger-level (enemy unit proximity) should be a factor at this stage. In my current thinking, I seed the map with focus points that provide information on the danger-level within their radius and then use this information to pass waypoints to the engine's pathfinding algorithm.

I'm sorry if I am not using the correct terminology, I am by no means an expert in pathfinding. I was just wondering what other people thought. Should the danger-level of a particular zone be included in the detailed pathfinding algorithm?

[imbaczek]

sometimes. ai wisdom 4 has an article about risk-adverse pathfinding, but it's not rocket science - just a simple modification of the edge weight function.

[ivand]

Indeed it should take into account threat maps, traffic jams, should be able to split group of units and merge them after, have several plan "b" options. It's very complex and I've never seen public description of algorithm which was able to handle all the stuff well in real time.

For me two biggest questions are"smart" rerouting and cooperative PF. What we are discussing here is first step to reduce computation difficulty by simplifying internal map representation.