🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Strategy AI Question
Author
I''m writing a strategy type game in my spare time, but I''m stuck at the pathfinding. I have a "high level" pathfinder which finds a rough path through the map, but now I need a "low level" one which will help the units navigate around other units, etc...
Units all have bounding spheres around them, and I have a grid like object holding all the units.
Right now, the units follow the rough path, and when they encounter an obstacle, basically just steer right or left to clear it, but problems like "U" shapes composed of units, a unit will get trapped in.
How would I go about implementing some sort of pathfinding here?
I''ve heard about using convex hulls, but I haven''t figured out how they would work here. Anybody care to help?
If you have the bounding spheres, how about allowing your program to link them into solid units (at least only in terms of obstacles)?
Like this:
| |
| |
|_ _ _|
9 units, standing as they are in a U shape. What your program can do is say that if the bounding spheres are close enough, they should count as one huge sphere. What happens here then is that as more and more link to this sphere, which might not be more than just some temporary virtual bounding sphere, just by being close to each other, you create a sphere around all of them like this:
(|) (|)
(|) (|)
(|) _ _(|)
//Um...imagine there are spheres around the bottom ones too.
The above would become basically this:
(U)
//Imagine the U above is the actual U in this example
So your units will ignore the ability to go into the U since the larger sphere will say it is not possible.
I see problems with this, and I do not have much experience with AI pathfinding, so hopefully someone else will have info.
Like this:
| |
| |
|_ _ _|
9 units, standing as they are in a U shape. What your program can do is say that if the bounding spheres are close enough, they should count as one huge sphere. What happens here then is that as more and more link to this sphere, which might not be more than just some temporary virtual bounding sphere, just by being close to each other, you create a sphere around all of them like this:
(|) (|)
(|) (|)
(|) _ _(|)
//Um...imagine there are spheres around the bottom ones too.
The above would become basically this:
(U)
//Imagine the U above is the actual U in this example
So your units will ignore the ability to go into the U since the larger sphere will say it is not possible.
I see problems with this, and I do not have much experience with AI pathfinding, so hopefully someone else will have info.
If the unit encounters an obstacle. (Doesn''t matter the shape), just make the unit "follow" the curve of the obstacle, meaning you let the unit go alongside the obstacle. By that, you can easily make the unit go around it.
Electron
Electron
"Your truth can be changed simply by the way you accept it."
Personally I would forget about low level pathfinding and work with some kind of flocking system. If troops are in formation that simply means they tend towards their correct position in the formation but can be pushed aside by obstacles in the world. By having repulsion from the individual trying to traverse their path onto the units they are trying to avoid, as well as repulsion from the units being avoided onto the individual trying to traverse the path, the units should simply move out of each other''s ways as they move through the world. This does depend on having somewhere to move to and you might want to make certain individuals repulse others more i.e. a tank repulses an infantry man more than the infantry man repulses a tank, but a general repulses _everyone_ more.
In theory, the units in formation will flock out of formation as an individual passes through them, then flock back into formation once they''ve passed.
If you want individuals to avoid troops in formation as well then you can also have the entire formation have a point repulsion eminating from its centre.
Hope this helps,
Mike
In theory, the units in formation will flock out of formation as an individual passes through them, then flock back into formation once they''ve passed.
If you want individuals to avoid troops in formation as well then you can also have the entire formation have a point repulsion eminating from its centre.
Hope this helps,
Mike
Author
Thanks for the replies.
GBGames: I''ve been trying to accomplish something similar to that using convex hulls,etc... but having difficulty computing these large bounding "spheres" quickly.
Electron: Couldn''t there be serious problems with just tracing around the obstacle? He might end up wandering for quite a while if he chooses the wrong way?
GBGames: I''ve been trying to accomplish something similar to that using convex hulls,etc... but having difficulty computing these large bounding "spheres" quickly.
Electron: Couldn''t there be serious problems with just tracing around the obstacle? He might end up wandering for quite a while if he chooses the wrong way?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
