1
\$\begingroup\$

I am trying to create a game that has player created obstacles which can be placed anywhere in free space, and which has a large amount of enemy agents. In persuit of maximizing the number of agents I can have active at any given time, and as a secondary goal of maximizing the possible size of my map, I found potential/vector fields to be a very appealing solution, except for one thing.

Since the geometry is not aligned to any particular grid I have the problem of what to do when I have a narrow alley between obstacles that is approximately the size of one of my units (As such:)

enter image description here

In this case, cells approximately the same size as the unit would consider this route impassable. One solution would be to use a smaller size of cell, but this of course means more computational resources. Does anyone know of an alternative solution to this problem?

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Since your geometry does not have to be axis aligned, an AA grid does not seem like a good data structure for the pathfinding. I think you can consider several approaches.

  • Adaptive grid - grid which will be finer close to non-AA edges and coraser elsewhere. Something in terms of quad-tree. The potential field would then work regularly and your grid would be axis aligned.
  • Convex polygons connected by choke points - if your maps will look like StarCraft maps, where there are mostly convex areas connected by chokepoints, you can do very simple navigation inside the areas and have special handling of choke points. This is not a solution by itself (it does not solve the problem), it's just an idea to think about.
  • Triangular or quad navmesh - if your maps will be more complicated you can partition the ground into triangles/quads which will not be axis aligned such as when working with navmeshes. Then in each of these nodes, you would have your vector field vector. Of course, some care needs to be taken when generating the navmesh since we would prefer equally sized triangles.
  • Steering - another approach different from vector fields is to implement steerings, where agents are attracted to goals and repelled from obstacles. Steering tutorial. Edit: if you are interested in different steering behaviors of multiple agents check out Boids. Also some more about steering from the same author here.
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.