next »

[Archibald]

There is a dungeon built with 3x3 rooms connected by corridors 1-2 tiles width. It's inhabited by several dozens of underground creatures that move around (so it's rather crampy environment). Let's say that each grid/tile can be occupied by only one creature at a time.

- Cheating is acceptable (like if two creatures block each other ways for too long they swap positions or they are allowed to violate the one creature per tile rule temporarily). But if it can be done without cheating it would be slightly better.
- I prefer if it is not too complex if possible, also I don't need a perfect solution (the units can appear a bit dumb and not always use the absolute optimal path, that's OK).
- Speed of the algorithm is of relatively low importance (but within reason).

How to organize their movement?

I think pathfinding probably should take into account only dungeon's shape (ignoring units/creatures), because it will end up in too many cases with "target impossible to reach" plus all these units move around all the time. Then when they encounter another unit they use some avoidance algorithm or use short range pathfinding which take into account both dungeon and units?

I'm also not sure how to define the target they want to reach. Units will frequently move to "rooms" and a room is 3x3, so not an exact coordinate. The most obvious would be to use the center of the room as the target, but if it is occupied by another unit it will be marked as not reachable which is not true since there are still 8 tiles left in the room.

[Archibald]

I know this is not known topic and there are no experts on this kind of subject. I don't expect brilliant answers/ideas. But you could try posting how would you solve it. Your solution don't need to solve it perfectly, if it is better than the one posted previously it's more than enough

[Xienen]

I know that in a 3D environment, this has been achieved by using cylinder collision between the entities and employing queueing systems at any choke points that exist in the world(where only 1 entity can move through the area at a time, such as a door).  The reason to use cylinder collision is that it inherently allows the entities to get past each other 99.9% of the time if they run into each other.

[Xecutor]

Use cheating and A* and you will be fine. IMO.
Tiles in a room should have 'some unit has choosen this tile as destination' flag.
When some unit is going to target some room it should start with center and search for a tile with unset flag. Once choosen, set flag, calculate A* path and follow it.
If unit was moved by 'cheating collision', it probably should recalculate it's path.
When unit changes it's route or is killed, flag must be unset.

[st33d]

Consider public transport.

People on public transport seem to adopt a hive mind. All moving to the same destination, sometimes notifying the person ahead of them that they can move forward.

You can get groups of monsters to "commute" by passing on target destinations to those who are in the way.

[Archibald]

In 3D they usually have it easier because they have predefined and static map. You can simply manually define choke points in editor and that's it. In the game I have in mind there would be a lot of destructible terrain, reshaping the dungeon by the players, etc. It might be extremelly dificult to define what a choke point is. Also, in 3D you most of the time have passages that accomodate more than 1 unit (so at least 2 way route can be created), in tile based there would be a lot 1 tile wide corridors which makes cylindrical collision useless.
But maybe instead of queue system make some priority system? Like a unit that waited too long gets a "priority passage" flag?

As for "some unit has choosen this tile as destination flag" I think better not. The distances will be sometimes high, so in some cases the room could be used and then freed by another unit before the one that wanted to use it first arrived. Also it would make rooms artifically cramped in case of traffic jams (the room would be fully occupied by flags of units that can't reach the room yet).
Or maybe set the flags only if the unit is really near the destination?

The crowd behaviour (hive) concept sounds interesting...


In game scenario:
There is a room in the north and a room in the south, connected by a very long 1 tile wide corridor. There are two units, the 1st is in the north room and want to reach south, the 2nd goes from south to north. The assumption is the engine does not understand the definition of "corridor". How to handle it?

I guess, with the 1 unit per tile rule it can't be done... They would either need to occupy the same tile for a while or swap.

But let's say there was a queue system implemented and it works. Now, wouldn't it look strange? I mean, it's not how it works in real life. You don't know that there is someone on the other end of a very long tunner, you just try to to enter the tunnel, unless you see someone almost leaving it (in such case you wait and the enter). But if the other person is somewhere far, far... you don't know it and enter, even if you expect someone is there, you hope to somehow miracolously avoid each other in the middle
So, I wonder id dirty cheap swapping position would not be better for gameplay reasons than perfect avoidance algorithm...

[Ashaman73]

In my game(3d) I use a combination of waypoint-path and steering behaviour(http://www.red3d.com/cwr/steer/). The basic idea behind steering behaviour is, that each agent has a movement goal (position or path) and that each agent checks it closest surrounding (walls other agents) to decide where to move.

For your problem I would sugguest to take a look at this behaviour http://www.red3d.com/cwr/steer/CrowdPath.html. When you let each agent always move on the right side of the path and utilizing this http://www.red3d.com/cwr/steer/Doorway.html behaviour to queue up at choke-points, a movement with little cheating should be possible.

[Archibald]

Just saw this on the DF's update log:

allowed dwarves to ride/push minecarts even when they don't have walking access to destination

So, it seems they decided to switch for non perfect pathfinding in order to avoid crowded tiles problem...

[RudyTheDev]

For non-crowd solution, one of the methods I have used is to use a time-dependent obstacle/collision checking. So, simply put, your obstacle map will be [x,y,t] instead of [x,y]. Then, once a unit finds a path for itself, it will mark that path on the map at the respective time steps and future path-finding will no longer allow those tiles only at those times. This works great for things like A*, because the processing is just as fast and you only need to keep track of how long your current path is.

Of course, too many time steps and a bigger map and you run out memory. Easiest solution is to ignore other units in "distant" future, and that works great when units are expected to be killed or change their minds.

The one problem this has is that you probably will want to have a cheaper "stay" movement option, so units can queue in bottlenecks instead of jumping back and forth between tiles while "waiting".

[rostok]

there are couple of questions and answers that should narrow the problem: how big is your map, how many npcs are there, is there a maximum distance to destination that npc will seek.

a* in changing environment can be implemented by adjusting heuristic function result with much higher cost for nodes that are inaccessible. either those destroyed or occupied.

but if you have a lot of ram to spare i would recommend to make a huge matrix that stores a precalculated optimal path info. it is quite huge (n x n, where n is number of nodes) but luckily symmetrical. matrix[a,b] stores next grid id if you are travelling from a to b. of course each time you change the level it should be recalculated. however not necessaraly whole but only parts that changed. but precalculated approach forgets about all dynamic obstacles.

[dougbinks]

Just posted about Recast and Detour on this thread, but I think Detour would be helpful here for your problem, see http://code.google.com/p/recastnavigation/. Mikko's blog has some information and videos which may also be of interest.

[Archibald]

there are couple of questions and answers that should narrow the problem: how big is your map, how many npcs are there, is there a maximum distance to destination that npc will seek.

I think the map would be max 1000x1000 (or less), but most of it would be impassable. A few hundred moving entities/NPCs (below 300 I think). As for max distance, hard to tell, but at least sometimes it will need to travel from one edge of the map to another).

Of these NPCs they will do some non moving stuff (like brewing potions, crafting) and all will have periods of idelness (sleep and rest).

[bateleur]

One thing to bear in mind is that once you have blocking creatures, "pathfinding" does not uniquely describe the problem.

In particular, suppose I am a creature that has a choice between waiting for one other creature to get out of the way or taking a fairly long detour. Which behaviour is better depends on not only the other creature's behaviour, but also on what utility profile I assign to different lengths of delay. If there are two or more creatures in front of me I also have to take into account that I might be blocking some of them in. Is that bad? If so, how bad? And so on.

[rostok]

blocking the way could be solved in to ways:
1. (cheating) if the next grid is occupied and creature there wants to step on my current grid we should swap. easy.
2. if the next grid is occupied and the creature there is idle i should step sideways. say i want to go north, then i step east. but always the same direction left or right.

(alternatively you can try to mix those two cases. and if the creature on next grid is idle you force her to swap based on some kind of priority like strength, speed, level etc.)

this is quite popular method for path-finding and npc will just try to circle around the obstacle. once the path to destination is free it continues normally. this is not the smartest code but very fast (if you will take advantage of this matrix with precalculated paths).

as of matrix size you can store only grids that are free, excluding impassable ones. that would greatly reduce its size. however you will have to use some lookup tables...

anyway this is quite intriguing, i would love to see some demo

[Danmark]

For non-crowd solution, one of the methods I have used is to use a time-dependent obstacle/collision checking. So, simply put, your obstacle map will be [x,y,t] instead of [x,y]. Then, once a unit finds a path for itself, it will mark that path on the map at the respective time steps and future path-finding will no longer allow those tiles only at those times. This works great for things like A*, because the processing is just as fast and you only need to keep track of how long your current path is.

Of course, too many time steps and a bigger map and you run out memory. Easiest solution is to ignore other units in "distant" future, and that works great when units are expected to be killed or change their minds.

The one problem this has is that you probably will want to have a cheaper "stay" movement option, so units can queue in bottlenecks instead of jumping back and forth between tiles while "waiting".

I agree that this is a good method for the case, but there's no need to explicitly store future obstacle maps, if you're worried about memory usage. You can store the paths per unit & look up that data as necessary. Besides, if unit paths change prior to completion, isn't there a big workload in keeping the future obstacle maps up-to-date?

With a "stay" option on paths as you suggest, the method is robust. Units can know exactly how long they'll have to wait to enter a tile, so will figure out a roundabout path if ideal.