Archived

This topic is now archived and is closed to further replies.

ageny6

A*

Recommended Posts

I just, just read the article on A*, and I just can''t seem to picture the algorithm in a more complex environment. That is, say we have 900 units per 900 units map. That 810,000 units to checks for the G and H to calculate the F. That''s way to much processing if the game has to be realtime. What is a man to do? My signature used to suck. But it''s much better now.

Share this post


Link to post
Share on other sites
Use waypoints. These are hardwired into the system by the programmer. They save computing time imensly. This is much better then using a algorithm like A*. When you use A*, you are calculating the path in realtime. If the path is already hardwired in, it goes much faster.
Hope this helps
BTW, I think Andre LaMothe has some good articles on the subject.

Share this post


Link to post
Share on other sites
quote:
Original post by ageny6
That is, say we have 900 units per 900 units map. That 810,000 units to checks for the G and H to calculate the F. That''s way to much processing if the game has to be realtime.


Huh? Are you saying the map grid is 900x900? That''s not big at all. I don''t understand why you are saying that you would have to do 810,000 checks - one for each map "square". Perhaps I am missing something in how you worded your post.



Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
I''d like to point out that A* is specifically optimized to not do unnecessary checking if your heuristic is a slight underestimate of the real cost of moving to your goal. If you have squares that don''t have the same cost, the A* algorithm will search along those squares that have a low cost first, unless the path gets expensive or of it''s very much in the wrong direction. The heuristic''s task is to guide A* towards its target, and therefore it reduces the space searched unless it has to search the absolutely longest path possible between obstacles.

Also you can make many other optimizations. You can have different landmasses, in order to disable attempts to move land units over water. You can also calculate one path for a group of units that are supposed to move along. And of course, you can use precalculated waypoints to save even more CPU cycles.

Share this post


Link to post
Share on other sites
Predetermined waypoints will not work with my current project. It's just the way it works out.

Let me formula the question into an example. Say we have player A, which is 900 to the left and 900 units above AI Player B (or AIB). There are lots of obstructions in the way and AIB must attempt to get to Player A. If you have to generate the path from AIB to player A every frame, will the A* algorithm demand a considerable amount of CPU processing?

Sorry for the cheezy question above. Hope this one clears things up.

My signature used to suck. But it's much better now.



[edited by - ageny6 on October 15, 2003 12:49:55 PM]

[edited by - ageny6 on October 15, 2003 12:50:35 PM]

Share this post


Link to post
Share on other sites
I can understand your situation, i made a comercial RTS game and this was a really hard problem.

Maybe the best way to solve your problem is to adapt others algorithms to your pathfinding process.

What we made to solve this problem is something like this:

1.- Subdivide the map in bigger "Zones", think in this like in an octree (we used Dijkstra's Algorithm to create zones with a determinated number of obstacles). The purpose of this, is to make a pathfinding search in a lower resolution map. (This process must be done in the map initialization)

2.- With this low-res path, create a list of "guide points", this is, create one point in each of the "Zones" touched by your low-res path, and use this to calculate sub-paths in the map (make a short path finding to the next point in the list). One little problem with this, is that your units have to know that this is not his final path, and that it have to calculate the next guide-point, but the advantage is that you reduce your calculations and divide them in smaller process.(this is a process executed by each unit when needed)

This process reduce your memory usage, process time and is really fast to use it with hundreds of units.

Hope this helps

---------------------------------------------
If God with me, Who against me?
Sitio de desarrollo de videojuegos en español
Digital Moon Studio...

There is no spoon

[edited by - NeonGE on October 15, 2003 1:31:18 PM]

Share this post


Link to post
Share on other sites
I understand the concept, but I can''t imagine coding it. At least not for the application I am currently doing. Breaking a specific area into larger zones is almost impossible because the zones always change, and some large zones that may seem impossible or invalid actually are, depending on where you (the player of AI) goes.



How can I determine if are large zone is valid if the validity of the large zone is dependant on manner in which the path in the smaller zone is taken?



Better yet, how do you determine the validity of movement of a large zone?

Thanks

My signature used to suck. But it''s much better now.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For such dynamic and context sensitive landscape, its better to use a pathing heuristic then. If the landscape changes as much as you say, how can the path the AI computed last frame be even valid beyond a couple of frames.

So instead just encode the AI with some simple pathing behaviors like move toward the target, and always turn right when someone is occulding etc.. and when it really gets stuck. Path only far enough away to get closer to the target and out of the obstacle.

It will take much longer for your agents to find their way to the target, but its a good compromise within such an enviroment and your CPU load will be managable.

If however the terrain doesnt change as much. Generate a course map, use that to path for a general path. When the agent encounters a obstacle in its path, it then recomputes a segment of that path around the obstacle but still tries to maintain itself on the original path. When it recomputes a path segment it uses the high resoultion map, and not the course map.

Good Luck!

-ddn

Share this post


Link to post
Share on other sites
An encountered problem is as follows:

The program I am working has as rules that a player can only move up, down, left, or right. No Diagonals. Implementing this concept with the A* algorithm made me think of a case scenario that would yeild an unwanted result (described below). Is this a good anticipation? Or with the A* algorithm simply ignore the problem below even with the movement constraints


Note, the boxes below look REALLY BAD when posted. Click on edit and the small map I want to visually express will be aligned properly.


say we have the following small map:

*----------------*
| |
| |
| |
| |
| |
| |
*----------------*

and we have player A and AI player B:

*----------------*
| B |
| |
| |
| |
| A |
| |
*----------------*

using the A* pathfinding algorithm, if I understand correctly, A* will give this path as B tries to move to A:

*----------------*
| B |
| * |
| * |
| * |
| ********A |
| |
*----------------*

Or something of the sort. But, wanting only movements of 90 degrees, the A* algorithm would do something like this:

*----------------*
| B |
| ** |
| ** |
| ** |
| *********A |
| |
*----------------*

Which is not what I am looking for (the rather weird diagonal line). Rather, for the project I am currently working on, it would be preferable to generate a path similar to the following:

*----------------*
| B************ |
| * |
| * |
| * |
| A |
| |
*----------------*

How can I modify the A* to prepare such a path? If even possible.

My signature used to suck. But it's much better now.



[edited by - ageny6 on October 15, 2003 10:48:24 PM]

[edited by - ageny6 on October 15, 2003 10:49:12 PM]

[edited by - ageny6 on October 17, 2003 12:32:14 PM]

Share this post


Link to post
Share on other sites
Please edit your post and encapsulate your ascii graphics between code tags, which preserves formatting.

As to your problem...

1) How much does the topology (connectedness) of your domain change between frames?
2) Is it merely that the location of the goal (the player) changes between frames?
3) Is it the case that both the goal location and the terrain topology are changing between frames?

(1) Means that you need to be able to handle the affects of altered path costs during execution. Check out D* (Stentz) or the much easier to understand LPA* (D* Lite) (Koenig).

(2) Means that you need to recompute heuristic estimates (or actual node-goal costs in a known domain) every time the goal moves. You could probably modify LPA* to do this. If you do, make sure you publish your result, as this would be a new and useful variation of the algorithm.

(3) Means you really are facing an uphill battle and it might prove more tractable to just use a local (reactive) search method, rather than trying to find a globally optimal plan. There''s plenty of literature on such methods online.

Good luck,

Timkin

Share this post


Link to post
Share on other sites
Things to bear in mind:

You don't have to use A* (or similar) for all an agent's path planning. You can throw in some reactive behavior into the mix to account for any small dynamic obstacles (like other agents)

You don't need to do an A* search for every agent every update-step. Spread them out.

If your agents are grouped (in a formation for example) you only need to do one search for the group.

You can reduce load spikes by splitting up each search over a number of update-steps. (using a reactive behavior to fill the short gap until a proper path is formulated)

Use hierarchical pathfinding with very large maps. I believe someone has already mentioned this.

You can post-process paths to smooth them (essential really if you are using a grid-like graph). An alternative - if using A* - is to tweak the heuristic to favor straight lines, but this is a much inferior solution.

Hope this helps


My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

[edited by - fup on October 16, 2003 4:41:58 AM]

Share this post


Link to post
Share on other sites
Nice topic!

Hey Ageny6, if you want to avoid weird staircase (diagonal) steps... do the following
1) Use the Manhattan Distance heuristic
h(goal.x,goal.y,current.x,current.y) = abs(goal.x-current.x)+abs(goal.y-current.y);
it looks like you were using the Euclidean distance before.
*AND*
2) change the cost function so that you have an extra cost for every turn (change in direction) that you do.

If you do this properly, you''ll get the straighter paths instead of your staircase path like in your nice picture example. =)


If your domain changes alot, you might want to try D* or LPA*, please tell me if they actually work. I''m sure Sven is curious to know if his stuff works too. I''ve tried them and I still haven''t found a good application for them yet. They work well only under certain conditions... and D* is a pain to program (so I don''t recommend it).

Good luck!

Share this post


Link to post
Share on other sites
quote:
Original post by Peter Yap
I''m sure Sven is curious to know if his stuff works too.



It certainly works in ''constructed'' grid world domains... as to whether it''s practical in a game... well, we''ll have to wait and see! Certainly with the increased CPU times available to AI these days, algorithms like D* Lite will start to see use over hybrid algorithms, like A* with local obstacle avoidance.

Timkin

Share this post


Link to post
Share on other sites
quote:
Original post by Peter Yap
Nice topic!

I try to bring the best to the community

quote:
Original post by Peter Yap
Good luck!

Thanks, i'll need it.




I do have one last question, though. Is verifying 900x900 units a demanding task for the CPU? In other words, will it take a considerable amount of time to find a path that goes from point 0,0(current) to point 900,900 (goal)?

Thanks

My signature used to suck. But it's much better now.



[edited by - ageny6 on October 17, 2003 8:34:43 AM]

Share this post


Link to post
Share on other sites
It depends on the obstacles and weighted regions in between. Alot of differently weighted regions will cause it to branch out more looking for cheaper alternatives, obviously taking longer.

Share this post


Link to post
Share on other sites
quote:
Original post by DrEvil
It depends on the obstacles and weighted regions in between. Alot of differently weighted regions will cause it to branch out more looking for cheaper alternatives, obviously taking longer


mmm...

Well, supose that the regions don't really have a weight to them. That is, they are either passable of impassible only. Will it make that much of a difference?

Also, what is meant by taking longer. I understand that this is totally dependant of processor speed, but how much of a difference will the "obviously taking longer" generated path be in comparison to a "normal" path per say (in terms of, for example, percent slower, or tick difference in order to remove the issue of difference in processor speed)?



My signature used to suck. But it's much better now.



[edited by - ageny6 on October 17, 2003 6:31:47 PM]

Share this post


Link to post
Share on other sites
With no obstacles and an accurate heuristic, the performance of A* will probably tend towards O(N) where N is the distance. 900x900 is not too big a region as a path of 900 units (or 1800 units, if you can''t go diagonally) is not all that long. If your heuristic is good and there aren''t a lot of dead-ends on your map then A* is going to work well. If there are a lot of dead-ends then no algorithm I know of is likely to work amazingly well, but preprocessing the map might help (eg. by biasing the weight of map nodes in favour of those in ''corridors'' over those in ''rooms''). It really is just worth trying the algorithm and then optimising it. Graphics cards draw more than 810,000 pixels per frame many times per second, so maybe an AI algorithm could process 810,000 nodes too.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Also if you used heuristic weight you can modify the results of A*. A higher heuristic weight causes it to behave more like best first and doesn''t "fan out" as much in the search, but also doesn''t give you as good of a path in most cases. It''s just a way to tweak the behavior a bit to between path quality and speed. I always prefer to keep the heuristic accurate, as it guarantees a path as good as Dijkstra’s if and only if the heuristic is not overestimating. The option is there though if you are willing to sacrifice a possible slight decrease in path quality for potentially thousands of nodes saved just by a very slight increase in the heuristic weight.

Share this post


Link to post
Share on other sites