I saw a lot of articles about a*, but not really a way to make it really fast. My idea is this: since the cost between tiles is always 2 or 3, then when processing a node, the maximum cost (f) to one of its neighbors is f[currentnode] + 6; thus, we can use a number of seven ques to insert the node directly to que[f[newnode]-f[currentnode]]; we only process que[0] at any time, and then when it's empty, we rotate the pointers, so that the old que[1] is now que[0]. We only care about the last node inserted in the que, so node extraction is o(1). Many nodes will be inserted in the wrong que at the beginning, only to find a shorter path to them later, so for each node we check to see if it has the f that the current que should have, so you won't have to delete it from a later que when a smaller cost is found. This seems to work rather well. I wonder if you had any ideas to make it better or faster. I don't have the book AI Game Prog Wisdom and I don't have the possibility to get it here, so I couldn't read the article "How to achieve lightning fast A*". If anyone could describe me the method there, or a better method than mine, I would really appreciate it. [edited by - madu on July 23, 2003 9:45:21 AM]

Just some points to think about...

quote:

---

Original post by madu
My idea is this: since the cost between tiles is always 2 or 3, then when processing a node, the maximum cost (f) to one of its neighbors is f[currentnode] + 6;

---

You''re obviously referring to a specific problem domain here, rather than the algorithm itself. One should always be able to find optimisations specific to a domain that can speed up the implementation of any search algorithm. If this one works on this domain, great! Go for it! You''ll find though that it is not suitable for other domains though.

Additionally, expanding a node from your OPEN list that is not the lowest cost node will violate the optimality of the algorithm, such that the first path returned to the goal will not necessarily be the lowest cost path.

Cheers,

Timkin

Yes, well, that is not what I asked. How does the pathfinding in games such as Starcraft of AoE works for example? How can you make it go fast for maps of up to 256x256, when there aren''t diffrent costs between tiles? And, what do you mean by expanding a node that is not the lowest cost? It always expands the nodes with the same f as the start node (que[0])(the heuristic is exact), then when all are finished, the nodes with the f+1 cost and so on. You don''t even have to care about a node''s parent or if it is in the que or not, you just care about its g. Then when the search is finished, you just follow the g''s back to the start. And it works well, perfectly actually, but it''s still kind of slow. I am a beginner and this was my idea, I just wonder how else it can be done.

Cheers,

Madu

What you''ve just described is Breadth First Search (BFS), rather than A*, which is an example of Uniform Cost Search. A* is optimal and complete, as well as being optimally efficient. BFS is not and offers no guarantees about the optimality of the path returned, only that it will return a path from the set of possible paths that do reach the goal.

As to not answering your question, I wasn''t attempting to, as I feel it is only something you can do, since it''s a problem-specific question... and you know the problem. I was trying to give you some things to think about while you searched for your optimisations.

If you feel I haven''t been helpful, then you have my apologies for cluttering your thread.

Timkin

Sorry, I was a bit rude. But it is not a BFS, it does not search in all directions equally. I have implemented BFS too, also with multiple ques (4), but I use it for other things like calculating and storing for each tile the minimum cost to the nearest storing unit where a villager can leave wood for example; so wherever you are on the map you can just follow the g''s back to the nearest storing unit - it will always be the shortest path possible without ever calculating the path there again. The algorithm I described the first time is pure A*, but built for the special case where a cost between tiles is always 2 or 3 and the heuristic is exact. I just use this special property that a cost for the next node cannot ever be more than the current cost (f) + 6 (as is the case when you go to the neighbor in the oposite diagonal direction and then back, 3+3), to store it directly in a que where it belongs so that it does not have to be sorted - a que always contains nodes with the same cost. Thus insertion is O(1), deletion is O(1), and selection is O(1). The multiple que method (well, stacks actually) is just a way of not having to sort the nodes to get the best one, but the algo is pure A*, at least as I understand it. It works, trust me, I am having a difficult time understanding why you don''t understand it. I don''t know if I could use it when h is underestimated, but I surely can''t use this method when it is overestimated. Yes, i am reffering to a speciffic domain, because that is what you would find in a game. This is the only way I could think of to use A* for a large map of 256x256; but i don''t know if it is fast enough; when it has to search all the 256 x 256 map, it is twice slower than BFS - 100 ms on my antique AMD K6 2 300 Mhz, instead of 50 ms. How in the world does the rest of the world use A*? That is my actual question. Sorry for talking too much.

One way I would optimize A* for an RTS-style map would be to reduce the problem size. You could group tiles that have no unpassable(which could be different for different kinds of units, so you might need multiple sets of groups) tiles in them and treat the entire rectangle formed by those tiles as a single space. It seems likely that there are such groups all over the map which could greatly reduce the number of nodes you need to search.

Also, I don''t know if you have a closed list or not, but if so, you should probably replace it with a bit field saying if a tile has been searched before or not.

Yes, I did thought about that. But I thought different sized linked rectangles would just raise delicate situations and in the end I just chose the node by node method. I also thought about studying passability around obstacles, since they are the only ones that can divert a path, going around one looking at the dest until you can''t see that obstacle anymore. But in the end I chose A*.

I have red that in AoE2 they use more path finders, one of which is for long distances and uses mimaps. Using mipmaps again raises questions, depending on the map. When do you choose a walkable tile in the mipmap, when even 2x2 tiles can have a lot of diffrent combinations, and choosing only 2x2 walkable tiles from the original might miss some information?

And no, I don''t have a closed list. I don''t need one. All I need to do is to check a node to see if I can give it a smaller g than it already has, I do not care even if it is in open or not. If it has a greater g, then I update it, update the f, and put it in the right stack (que[f[newnode] - f[curnode]]). If it had a greater g, that means either it was not in the open list (one of the stacks), or it was in one of the other stacks but a shorter path was found to it. I don''t even have to delete it from the stack it was in, all I need to do is to check if the currently processed node in que[0] still has the f this stack should have or if it has a smaller one and it was processed before. And at the end, I just track the g''s back to the start, from smaller to smaller. Why would I even need a closed list? I would need to ckeck the node''s g anyway.

My apologies on labelling it BFS. You''re description sounded like BFS because I had misunderstood your data structures. I believe I understand better now what you have implemented. As to optimising it, I''ll have to map it out on paper...I have a think about it at lunch today.

Cheers,

Timkin

There are a number of ways to speed up A*, but most methods address issues beyond the A* algorithm itself. Firstly, modern games don’t use uniform grids anymore, (and probably haven’t for the last two years). The problem with a uniform grid is that you sometimes have sparse areas containing a high number of needlessly redundant nodes. Instead, think about building an arbitrary navigation mesh. The node information is exactly the same and the algorithm remains unchanged too. Most games include some form of debug mode where a designer runs through the world and presses a button or key to place down nodes, (it only takes 10 minutes to do this for the most complex worlds). You then walk the map with an accelerated version of a game Avatar, (player, ship… whatever), using the same physics and collision that your characters normal use. Each node is taken in turn and an attempt is made to walk from the source to every other node in the world, (obviously you need to limit the number of branches allowed per node). If you take a room for example, a uniform grid may cover the room with many nodes, but with an arbitrary mesh you only need a node in the center of the room and a node in the center of each doorway. If you have an object in the middle of the room like a table, place a node at each corner. This adds an inherent optimization: You search far fewer nodes than grids.

Secondly, most games include some form of caching system. When you generate a path to follow it usually ends up being a simple list of node indices. If you have a massive node map it’s beneficial cache the last several paths your game Avatars have generated. In most games, many characters are chasing the player or heading in the same direction often sharing the same node list.

Thirdly, stop using pointers and open / close lists. If you create an indexed pool of nodes and link them together by an array index instead of pointers you’ll save a lot of frame-time, (just use a bit on the indecies to flag open / closed nodes). When you’re stepping through a list of pointers, unlinking and re-linking to different lists you’re usually trashing the cache, (especially with the crappy MIPs in the PS2 ;-) You can also save memory here by using 16-bit integers to index an array rather than 32-bit pointers.

Check out the book “AI Game Programming Wisdom” (ISBN 1-58450-077-8). It has a number of chapters on how to optimize A*, none of them refer to the algorithm itself however. When you have any kind of heuristic involving a great number of samples, cutting down the number of samples you process and changing the way you store those samples is the best path to optimize.

---
Strange


[edited by - strangebreed on July 15, 2003 4:17:03 AM]

Sorry, forgot one more thing...

Make sure that you only A* when you absolutely need to. For most FPS style games you can use a general avoidance algorithm to negotiate the world much faster than generating an A* path. If you hit something, or positively get stuck using general avoidance then use A* path-finding as a last resort.