Any tips for obstacle avoidance etc.?

Game Mechanics Artificial Intelligence
#1

Seeking your wisdom ;D

I have a tile based grid, and pathfinder that returns me a path of Nodes in a List. Everything works fine, but!

When I select 2 or more units and tell them to go to some tile, then they will all group together at the end and appear as ONE! They are all occupying the same tile.

This is of course a very old problem and has been solved kazillion times, so I don’t want to invent a new solution kazillion+1 times. Please tip me off how I can solve this, maybe this is a very simple problem.

I was thinking about something like:

  1. If unit has a path that it is following, verify that there are no obstacles in path. If there are obstacles get new path to goal node.
  2. If goal node is occupied, find a new goal node that is the nearest unoccupied node to the original goal node.

But doesn’t seem to be working… :expressionless: maybe I did this wrong.

#2

Try Lee’s algorithm . A faster,but a little harder is Dijkstra’s algorithm . Google for these … :wink:

#3

Increase the cost for planned / recently traveled nodes and their immediate surroundings.

#4

Sounds better the more I think about it, might be some problems with this, but I’ll try this.

But “Immediate surroundings”? Like for every node in the path I shall increase the cost of all its neighbouring nodes also?

#5

You could use a reservation table - see here (there’s some other ideas there too)

#6

Great link, thanks :slight_smile:

#7

Yup, to spread the units naturally, but keep them kinda grouped at the same time.

If you’ve ever played Cossacks, you might have noticed the wonderful AI. They used cost-algorithms that did not only take terrain into account, but also their own and the enemies ‘influence’. Just as much as they attract eachother, they will repell.

Just take the average walk on the street, you can pretty much visualize the influences and the ‘logical’ path you travel through people moving at different speeds and in different directions. You don’t need interconnected nodes, just a couple of Vec2[128][128] and Vec1[128][128] for different kinds of influences, which will influence (yet again) the travel-cost through the nodes.

Note:
I’ve never implemented this myself, hardly any pathfinding, except quite fancy gridbased floodfill. So if there are giant practical problems, don’t blame me :slight_smile:

#8

To clarify a bit:

When a lot of units travel South-West to North-East, the influence-map for ‘moving in that direction’, becomes stronger and stronger. That way you won’t see any (of your own) units moving through your formations, they’ll try to avoid and walk along side.

Calculate the impact by: unit-heading DOT map-influence-vector

http://katav.nl/pathfinder.png

#9

Maybe I explain what I finally did.

I basically decided that obstacle avoidance (e.g. avoiding going through/over other units) was a waste of time, so units can now travel over each over.

I however made the game so units don’t share the same tile! So if I were to select and tell a number of units to go to the same tile location, they would not end all on the same tile. I added a “reserved” boolean in my “Tile”;

  1. The first (to run in the program) unit sets the goal tile as reserved, and a path is found between start and goal.
  2. The 2nd unit sees the goal tile is reserved, and now I use Dijkstra to find the nearest tile (new goal) that is not reserved and reserve it for that unit, and find a path between the start and the new goal location.
  3. The 3rd unit and up does exactly the same as the 2nd unit.

It’s very nice and works! :slight_smile:

#10

And if you give your game a magic-theme, you can get away with it. :stuck_out_tongue:

Not so much a technically outstanding achievement :wink:

#11

The simpler and more intuitive solution to the problem the more time you can waste debugging something else :wink:

DP :slight_smile:

#12

Hehe… well, it was either that or spend all my holiday vacation studying flock movement, sharing of paths and unit cooperation of moving (e.g. in narrow corridors).

I simply redefined the problem :slight_smile: I’d rather have something work than nothing. Besides, I can always revisit this problem later. My game isn’t a commercial one anyway.

My achievement :wink:

#13

maybe you already know or dont care about your problem anymore, but here is an idea :
for each tile define an occupied or not state with a time (or a num turn or a num frame) if turn based using a 3D array.

so basically the problem get one more dimension, use a 3D array for path finding, the third dimension represent time (or turn or frame). so when you look for a path you look in the 3d array, when you select a path you put it in the 3d array as occupied.

NB: your 3d array must loop to avoid a two huge third dimension.

dont know if I well explain myself :(, but hope it is undestandable as it may be pretty simple to implement.

this solution have advandage of taking care of unit speed and is very easy to implement and understand, also I guess it should work perfectly ;).

#14

random idea:

group units that travel to the same place.

model the group as a drop of liquid.

make the liquid change shape by changing the formation of the units accordantly and as necessary to move though the obstacles. perhaps even breaking of in two parts.

#15

Sounds like you’re inventing a new problem to me :slight_smile:

#16

yes which leaves you with two problems instead of one but both are simpler to solve as a whole then the other. added benefit is that units behave more natural: they stck together yet spread out enough to overcome obstacles. it is also makes more sense when the enemy clashes upon one an other an additional feature is that you can implement differed formations easier. I’ll see if i can reserve some time to whip something up, before I pass it on as advise.

#17

[quote]model the group as a drop of liquid.
[/quote]
:smiley: Just a simple implementation of the Navier-Stokes equations, rememeber to use semi-Lagrangian methods so it runs in realtime. Peice of cake