Pathfinding for large units
Author
Hi all. I'd like to implement a pathfinding algorithm for a 2D map; I've already tested A* and would like to use that.
However, I want to generate paths for units/players of varying size.
My grid is the size of my smallest unit/player, so that player can move to any "open" grid square. Say, though, I have a larger player that takes up 6x6 grid squares, and a 2 square wide open path in my map. Of course, that player would not fit down that path.
How do I implement this path limitation for larger players? I haven't seen anything that covers unit size... or am I missing something in the A* spec?
I thought about precalculating the path, which would work for the most part. However, if during game play I have a 6 grid wide corridor with a 1 grid wide unit standing in the center of it. In this event, my algorithm would allow the larger player to walk around the 1x1 player and "clip" into the wall. I'm still thinking of ways around this, but would appreciate any feedback from someone else with pathfinding experience/ideas.
Thanks,
Dennis
Edited by - chdennis on January 23, 2001 4:52:01 PM
When you come to generate the next set of nodes based upon the current node, instead of adding each adjacent tile that is passable, only add adjacent tiles that will allow a unit of that size to walk onto them. So, for a unit that is 5 wide, it would only let you go north or south onto a tile if that tile had 2 passable tiles to either side. And so on.
Author
How insanely simple. I''m my own worst enemy when it comes to over-complicating things.....
Thanks!
Thanks!
Hey dennis, where would I go to find an article/C++ code documenting how an A* algorithm works? Thanks!
-=~''''^''''~=-.,_Wicked_,.-=~''''^''''~=-
-=~''''^''''~=-.,_Wicked_,.-=~''''^''''~=-
hrmm nevermind, I''ve finally found one at:
http://www.gamedev.net/reference/articles/article690.asp
but if you guys know of any better resources, please let me know!
-=~''''^''''~=-.,_Wicked_,.-=~''''^''''~=-
http://www.gamedev.net/reference/articles/article690.asp
but if you guys know of any better resources, please let me know!
-=~''''^''''~=-.,_Wicked_,.-=~''''^''''~=-
I''ve found this site to be useful.
http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html
It has alot of resources related to A* and game programming.
-ddn
http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html
It has alot of resources related to A* and game programming.
-ddn
I don’t know if I’m stating the obvious or not, but kylotan has the right idea ;-)
I’ve used this method in the past, but make sure it’s incorporated in your node map generation stage. Each node has a list of the other nodes around it that can be traveled to, but also add a maximum width to each node path at generation time, (this complicates your node walker, but it’s worth it).
Run-time it’s then really easy to invalidate a node. You start your traversal with not only a start and target position, but the maximum width of the unit that needs to go there.
Here’s another cool trick I’ve used.
I added a load to each node specifying how many units can actually travel along a certain path at any one time. If your unit is traveling from node 100 to 101, then both of those nodes are loaded slightly. When the unit is past those moving from 101 to say 102, then the load on node 100 is reduced. You can adjust your node search so that routes like this seem more unfavorable than other routes when there is a lot of traffic.
Let’s say you have a whole column of guys trying to get through a narrow canyon. They could all try to get through the gap at the same time and bring down the system. By biasing the nodes that are being walked, some of your units will favor a longer route…. Basically for free, some units go through the gap and when congestion mounts, other units find a different, longer route around the canyon. If they can’t find a route then they wait for the other units to go through…. It’s “congestion AI” almost for free ;-)
It makes your unit movement look really intelligent.
---Strange
I’ve used this method in the past, but make sure it’s incorporated in your node map generation stage. Each node has a list of the other nodes around it that can be traveled to, but also add a maximum width to each node path at generation time, (this complicates your node walker, but it’s worth it).
Run-time it’s then really easy to invalidate a node. You start your traversal with not only a start and target position, but the maximum width of the unit that needs to go there.
Here’s another cool trick I’ve used.
I added a load to each node specifying how many units can actually travel along a certain path at any one time. If your unit is traveling from node 100 to 101, then both of those nodes are loaded slightly. When the unit is past those moving from 101 to say 102, then the load on node 100 is reduced. You can adjust your node search so that routes like this seem more unfavorable than other routes when there is a lot of traffic.
Let’s say you have a whole column of guys trying to get through a narrow canyon. They could all try to get through the gap at the same time and bring down the system. By biasing the nodes that are being walked, some of your units will favor a longer route…. Basically for free, some units go through the gap and when congestion mounts, other units find a different, longer route around the canyon. If they can’t find a route then they wait for the other units to go through…. It’s “congestion AI” almost for free ;-)
It makes your unit movement look really intelligent.
---Strange
That''s basically a very good idea, but be careful when implementing it. You might end up with silly situations like in many RTS where some units take a _much_ longer route just because a canyon/bridge is temporarily jammed...
Just make sure your weighing system between longer routes / jammed routes is balanced.
cu,
Prefect
---
Sanity is the trademark of a weak mind.
Just make sure your weighing system between longer routes / jammed routes is balanced.
cu,
Prefect
---
Sanity is the trademark of a weak mind.
Right ;-)
If your longer route found is more than 125% of the original, then you probably just want to sit and wait for the jam to clear.
The method does work well with FPS/action games though. Imagine you run around the backof a building with two guys following you and a third baddy goes around the other sode of the building and meets you face to face when you turn the corner. It''s quite a cool trick for very little additional programming.
---Strange
If your longer route found is more than 125% of the original, then you probably just want to sit and wait for the jam to clear.
The method does work well with FPS/action games though. Imagine you run around the backof a building with two guys following you and a third baddy goes around the other sode of the building and meets you face to face when you turn the corner. It''s quite a cool trick for very little additional programming.
---Strange
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
