Advertisement

Wall Avoidance

Started by January 25, 2011 04:34 PM
15 comments, last by IADaveMark 13 years, 9 months ago
So wall avoidance. We're doing a 2D top down shooter. And when AI characters enemies are wandering round they need to not run into walls.

The way i was gonna do it was to have a point ahead of the character. Then if that intersects with a wall return a point perpendicular to that wall away from the wall and have the AI char move towards that. To check if it intersects with a wall ill need to have an array of all the walls on the map. Then have an algorithm that will only check ones within a certain distance.

Is that okay, or is there a better way to go about this? We are using XNA if that makes any difference.

Cheers
Rather than iterating through an array of walls, can you simply just do feelers via raycasts? It if hits anything, steer away from it.

Some of these might come in handy.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Advertisement
One possibility is to use potential field method, such that the areas near the wall have high potential values and emit repulsive forces, which push the character away. You may want check the following potential-field-based obstacle avoidance papers.

  • [font="arial"]Khatib, O. Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Rob. Res., Sage Publications, Inc., 1986, 5, 90-98. (link, PDF)
  • [font="arial"] [font="arial"]Helbing, D. & Molnár, P. Social force model for pedestrian dynamics. Phys. Rev. E, American Physical Society, 1995, 51, 4282-4286. (link, PDF)
    However, the negative side is that the character will often get trapped to local minima, especially if it is not equipped with a good long term planning.

One possibility is to use potential field method, such that the areas near the wall have high potential values and emit repulsive forces, which push the character away. You may want check the following potential-field-based obstacle avoidance papers.

The problem with that method is that you are generating repulsive forces for all walls regardless of whether there is an agent nearby. To paraphrase a buddhist saying, you don't cover the surface of the earth in material to keep from cutting your feet on rocks and twigs and stuff... you cover the soles of your feet. In this case, it is the agent's responsibility to check for walls (and other obstacles) that lie in his path or in close proximity. It is not the obstacle's responsibility to continually update and broadcast their existence.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

@IADaveMark
Yes, it is also another problem, but actually it is still possible to calculate the forces by only taking some nearby obstacles into account. My drowsy logic (already past midnight here) comes up with two methods:

  1. Create a 2D grid, and for each cell of the grid, keep a list of the walls inside it. Then, .for each character, detect the walls lying inside the cell where the character is in, and compute the respective forces. Some neighbouring cells can also be considered. Or, ...
  2. Cast some outward rays originating from the character to detect nearby walls. Pick the walls with the hit points closer than certain threshold, then compute the forces for those walls.

But now both of them seem like inefficient computations to me. Also, the second idea seems similar to yours, the difference being you further use Reynolds' steering mechanism, instead of potential field. Anyway, I will second the idea of using Reynolds' wall following or obstacle avoidance behaviours.

PS: Confession: apparently potential field is the first technique I can think of when I hear about a wall / obstacle avoidance problem, even though I don't personally like this method...
Have you considered just using A* or similar to pick where to walk? These algorithms are well documented, tried and tested, and will do what you need to do.
Advertisement

Have you considered just using A* or similar to pick where to walk? These algorithms are well documented, tried and tested, and will do what you need to do.

Depends on how dynamic your environment is. Also, graph-based A* in fluid combat shooter situations can look very robotic. A navmesh would work better than a graph, of course, and give you the fluidity of movement that a local steering option does.

The reason I answered with a steering solution is because that's what the OP was asking about.


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Cheers for the replies lads.

The reason im using wall avoidance other than path finding is that the AI will just be wondering around the level until they see a player. So there is no set place for them to go. I could random a point and move towards that, but like is said above that can be robotic looking.

The ray casting idea i thought was gonna be awkward. But we are using a physics engine in this game. Its my first time with one so im still getting used to it. I think I just have to make a point at the top of the ray from the character a physics object. That way the collisions will be done by the physics engine and then i just move away from the collision.
I remember addressing this problem in a robotics course. One solution they used to overcome this problem was calculating the center point between each corner on the map and using it as a waypoint in the path. Not the shortest path by any means, but did a good job at missing walls and fairly easy to implement. Or perhaps tweaking A* such that areas near walls are given a higher weight so they are less likely to be added to the path?

Rather than iterating through an array of walls, can you simply just do feelers via raycasts? It if hits anything, steer away from it.
[/quote]

What advantage do multiple raycasts have over say a radius (sphere/circle) of influence?

This topic is closed to new replies.

Advertisement