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
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]
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]
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!
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!
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
Author
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]
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.
Author
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]
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]
[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
