next »

[meanwhale]

Does anyone has experience of programming crowd pathfinding? I think it's a nice and easy way to make game characters to find their path in a natural looking way, but I'm still missing some ideas how to improve it....

I uploaded a small crowd pathfinding demo of my new RTS game project. You can edit terrain, point units a target, and see how they find their way around in environment you created. Units don't use pathfinding algorithm like A-star, but instead try to walk straight to the target, and start wandering around obstacles when they meet them. Also they can ask their comrades to move, so that crowds don't get stucked in tight spots.

My goal is to make crowd movement look more natural and fun, unlike A-star for example, which makes units to move to the target optimal route. In addition, this way I avoid problems involved with changing environment and moving obstacles (i.e. other units).

Animation etc. are still quite rough but try not to care about it Give it a try and tell me your opinion! My future plans for the pathfinder is to make units to send signals when they are making progress towards the target, and on the other hand tell others if they are stucked so that other units nearby can make better decisions.

http://stonewallgame.appspot.com/

[kamac]

Looks nice. Would require some additional communication if it was an RTS game, though. For example, a team made out of five units wouldn't want to split, so one leading unit would have to choose the direction, and others would have to stick to it.

Looks way more natural, though.

@EDIT
Sometimes they're moving really dull, though. For example, four guys went straight to the point, while other got stuck at the wall and made a loop throughout the building to get inside  

Also, most of the time they're acting like they're blind Trying to go into a wall instead of turning right where the space opens. You should probably add something like fore-seeing things.

[meanwhale]

Thanks, good points! I think they will look smarter when I add some communications between the units (signals between nearby units). They act quite similar when hitting a wall and hitting another unit. They should preferably wait for another units to move, instead of wandering around. But there's a lot of trial and error involved in tuning a pathfinder

[meanwhale]

I updated the demo. Now you can see in which state units are (text), and a red square where unit asks other unit to move from its way. Have fun http://stonewallgame.appspot.com/

[BorisTheBrave]

Unrelated, but I think "stonewall" is already taken as a name:

http://www.stonewall.org.uk/

[meanwhale]

Thanks for heads-up I thought it's quite a common name but I like it anyway, so maybe final name will "Defender of Stonewall" or something epic like that 

[NinthPower]

You may want to also apply some Boids principles to help them stay together:
http://en.wikipedia.org/wiki/Boids
http://www.vergenet.net/~conrad/boids/pseudocode.html

looks cool!

[Gregg Williams]

Generally the problem with just using basic steering is that they will get blocked forever if there are complex obstacle shapes. Like a "U" type shape, or a river that needs crossed via bridge, etc.

[QCPolmer]

Looks good.

They seem to be clumping up a lot... 
Maybe make a large non solid invisible box around each of them when they move,
 where if they overlap another objects box (Another moving object),
they try to move away from where the boxes intersect?
Like a reverse gravitational thing around the ones
that are moving.

Also, maybe set up blocks that the crowd could walk over
that work as pathways. 
(like either go up or go down while over this block )
This would keep the crowd away from the walls at times.

[meanwhale]

Good points! I have to explore that Boids thing more

I think it's a good idea to make AI work different depending on game character's type. For example some swarm-like crowd could use simpler, more straightforward algorithm than smart ones. Also, some characters could have more personal space, whereas others tend to clump up. It gives game characters personal traits in addition to graphics. Crowds controlled by the player should act quite straightforward. It's so frustrating if a group controlled by you try being too smart but end up doing something stupid 

[meanwhale]

I have improved my crowd pathfinder quite a bit! I got ideas from ant pathfinding where ants spread out pheromones when they find the target, and then others follow the pheromone traces. In my solution pheromones are replaced with something I call beacons. Group of units start wandering towards a target. When some unit finally finds it, a beacon is set to the point the unit see it. And when some other unit sees that beacon, another beacon is set. Then group members can find the target by following the beacons. Beacons have a priority (B0, B1, B2, …) which tells how close to the target a beacon is.

I’m not sure if others use this kind of a technique, but it seems to work quite fine! The crowd moves naturally and usually most units find the target quite quickly after one has found it. Small groups can still get stucked in corners and do some merry-go-round, but that’s just lack of fine tuning...

Go check it out!

http://stonewallgame.appspot.com/

[nikki]

I''ve had some success of combining the steering Boids things with A* in the past.
just make the boids follow a path (one of their features(arrive at)) that you've generated using a*

[meanwhale]

My aim was to make crowd movement towards target look natural, rather than be efficient. Now the units seem to find their way around simple obstacles but they suck in labyrinth solving. That's where A* is the way to go. Crowd pathfinding's advantage over A* is that it doesn't need heavy pre-computing, which could be a showstopper if there's a large group of units who wants to call A* all at once. In addition units act naturally when environment changes, i.e. road blocks appear and disappear, and other units move on unit's way. Changes don't affect on crowd pathfinding whereas A* need recalculation.

[diegzumillo]

I once implemented a crowd navigation system that works by first calculating a 2d field. My implementation was crappy but this type of algorithm has the advantage of costing the same (almost) independently of the number of units. It does depend on the size of the terrain though.

Old video I made:



edit: forgot to mention, if you want to know more about this method I can find you the papers I used!

[Decent Machine]

Take all units as a "mass", find the closest unit in the mass to the target position. Run an A* for that person to the target. Run an A* from rest of the unit's to the closest unit and stitch together the whole path for all. If a unit is too far away (some threshold) from the center mass, let them run their own A* to the target. Now add some steering behaviors to the group along the path and you got something that can work for both open areas and small corridors.

It is at least one way to go about it, where you save a lot of performance because the paths from the units to the closest unit will be rather short. Is it easy to get right? NO  

[nibelheim]

This is really cool.  Two things come to mind:

Swarm Behavior:
I've seen some videos and read some articles on swarm behavior in nature (http://en.wikipedia.org/wiki/Swarm_behaviour#Mathematical_models).  I wonder if that might be useful here?

Ted Talk:
I remember a Ted Talk on AI (although I can't find it) that showed an example of robots that appeared to express social behavior when in a room together.  It turns out it was all a simple light-censor response algorithm.  But the affect was to make it appear like they were moving like humans did in crowds, even being "polite" and waiting for one another.  If you could dig up that video it might help.

[doihaveto]

Does anyone has experience of programming crowd pathfinding? I think it's a nice and easy way to make game characters to find their path in a natural looking way, but I'm still missing some ideas how to improve it....

I uploaded a small crowd pathfinding demo of my new RTS game project. ... Units don't use pathfinding algorithm like A-star, but instead try to walk straight to the target, and start wandering around obstacles when they meet them.

Oh man, there are so many interesting ways to do this stuff, some of which I've done, others I'm looking for an excuse to do...

Off the top of my head:

• Potential fields + edge following. As you mention above (go towards goal until you hit an obstacle, then follow the obstacle edge until you get a clear line of sight). It's so simple, and works surprisingly well in many cases! I do like solutions based on potential fields, like this one, a lot. But it can get into weird failure cases, like going around a column without ever getting a clear line of sight to the goal...
• Flood-fill + density. This one is for the case when there's one destination that everyone's going to as a crowd. First, do a flood fill, so you know the base cost from each cell to the destination. Then start moving agents, following standard gradient descent. But as they occupy each cell, they should bump up its cost, and when they leave, bump it back down (and maybe update neighbors as well). This way other agents will notice high-density cells, because they suddenly have higher cost, and avoid them. But this can also lead to local minima (which might be okay).
• Steering that incorporates A*. Make an A* path to the goal, and a "leash" that follows the path at a constant rate, pulling the agent with - but the agent also gets repelled by other agents nearby, and pulled in by the centroid of the group. As long as the leash is elastic, it can lead to pretty nice behavior.

On top of that, there's a question of formations. If you want to maintain a formation (e.g. 3x3 squad of soldiers), do A* for the centroid of the formation, and have each agent follow the path + offset for their position in the formation - eg. using the steering + path following technique above.

I don't think I have any papers ready as reference, but maybe I can dig up some...

[meanwhale]

Interesting methdos! Here's some flood-fill-like pathfinding from real life:





Actually that'd a cool element in a game! Like intelligent (Starcraft) creep 
My premises for the pathfinding was

• no pre-processing (like in A*) and
• no collective data/intelligence among crowd members

Units only have limited (radius) vision to environment, other units, etc. Communication between units happens thru signals (now they can just ask other unit to move), and in this case, beacons.

It'd be great if different kind of units/enemies behave differently, not just look different. Maybe I experiment with some other type of crowd/swarm behavior too, as they look so fun! After all I'm trying to make a fun game here

[meanwhale]

Hello! I started working on a new kind of a pathfinder, but ended up making a RPG/RTS game
It's based on that demo but currently pathfinding is maybe the worst part of its AI..... Will be fixed!
Give it a try:

http://stonewalldemo.appspot.com/

Longer post here:

http://forums.tigsource.com/index.php?topic=46663.0