Jump to content

  • Log In with Google      Sign In   
  • Create Account

massive pathfinding


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 fir   Members   -  Reputation: -460

Like
-1Likes
Like

Posted 15 March 2014 - 11:10 AM

I tested a* once but a* has some big cost per character

 

now i need some simple/cheap steering routine that 

could lead thousands of characters to some destination 

at highrates 1000 fps etc, so it should be as cheap as 

possible  (I am speaking about movement on a square tile map large amounts of characters at once, cost of the test if tile is free is cheap map[y][x]==0 test)

 

- should go round simple obstacles but not nescessary harder ones

- should be simple and quick (should also be continuous i mean no  jumps just from tile to vicinity tile)

 

i tried some basic aproaches

 

1) go just in direction of destination

 

+  it is at full speed and very cheap

-  it makes characters block each other after the one that reached the destination (can form a large queues/lines at the destination point not round group as expected ) (I need round group)

 

2) go to destination and if blocked rand one of 8 viciniti tile (I called this viciniti tiles ring 1)

 

111

1@1

111

 

+ it is also full speed at progressive movement

+ when the blocking shape is formed its randomisation makes

it erode and goes more to round shape, but

- this errosion goes at much lower speed than prograssive movement

(I need it at almost full speed preferrably)

- is unstable (I mean at the end blocked chracters at the edge

continue randomized movements

 

3) I tried the approach, of testing all free tiles ring1 then chose the one with lowest distance (sqrt(dx*dx+dy*dy)) then go (also with randimisation or without) but as far as i remember* it aslo not working good as expected 

 

- was blocking (though probably less)

- was unstable

- was computationally heavier

 

*I must test it yet (I was doing couple of days ago and i forgot exactly

how ot worked)

 

To sum up - I was in trouble with making the wanderers form something like round shape near the destination (not coliding each other and blocks itself) - also need something stable at end (it was a very initial approach so i was not even tried to calm tgis down at the and, but need something 

that will

- do it fast,

- made round shape group at destination point,

- will calm all the group att the end

 

form some possible options of doing this i need to chose faster 

one, *

 

this is at all fun problem, some hints or advices ?

 

 

 

 

* I also could prefer not 'cheating' algorithms I mean each of

character could only know the destination points and behave

with is own routine, not more complex routine that will treat it and move all as a group (but this one is weaker, and i may give up this for performance reasons but would like to know indyvidual routine working)


Edited by fir, 15 March 2014 - 11:19 AM.


Sponsor:

#2 wodinoneeye   Members   -  Reputation: 820

Like
0Likes
Like

Posted 15 March 2014 - 11:33 AM

Do your units know they are in a group or should usually be grouped .

 

You may be able to do something as simple as  move a little slower (towards the target) unless I have someone next to me and maybe to bunch em up more move a little faster if I have 2 people next to me.

 

Include with that NOT to slow down when blocking type content of sideways adjacent terrain (no change to tensd towards a group)

 

Faster/slower may be a random change of moving each turn if the moves are all in quantum steps.

 

Similar may be a random (once in a while) move adjustment to get closer to another unit (a 45 degree off direction of towards actual target  towards a nearby unit.  

 

Overtime the unit  may bunch up sufficiently


--------------------------------------------Ratings are Opinion, not Fact

#3 Waterlimon   Crossbones+   -  Reputation: 2565

Like
5Likes
Like

Posted 15 March 2014 - 11:51 AM

First off, you could create a pathfinding 'map' by flood filling from the goal with the agents ignored.

 

This flood fill will create a map where each tile tells how far it is from the goal (if a path is followed)

 

You can use this map to pathfind to the goal from anywhere on the map (agent will look at surrounding tiles and move to the tile with shortest distance value that was written by flood fill step)

 

IF agents could ignore each other and walk through each other, you would get O(1) pathfinding with respect to agent count since the flood fill is only done once and the same data is used by all agents.

 

 

But your agents cant go through each other, so you need some kind of local steering thingy, similiar to what you had already. I believe you can get it to work with some adjustments or some clever techniques.

You could for example have the agents follow the 'global' flood fill distance map if possible, but if they cant find a direction that goes closer to the goal, they would stay. HOWEVER, for the agents which have not been surrounded by other agents and have more than 1 'free' direction to choose from (but none gets closer to goal) you could after a random time delay apply local limited range pathfinding to look at a larger area and see if the agent could walk around some small obstacle to get closer. This would mostly get applied when the agents start clumping up and would essentially cause some of them to walk around the others to the thinner side of the agent clump.


o3o


#4 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 15 March 2014 - 12:35 PM

First off, you could create a pathfinding 'map' by flood filling from the goal with the agents ignored.

 

This flood fill will create a map where each tile tells how far it is from the goal (if a path is followed)

 

You can use this map to pathfind to the goal from anywhere on the map (agent will look at surrounding tiles and move to the tile with shortest distance value that was written by flood fill step)

 

IF agents could ignore each other and walk through each other, you would get O(1) pathfinding with respect to agent count since the flood fill is only done once and the same data is used by all agents.

 

 

But your agents cant go through each other, so you need some kind of local steering thingy, similiar to what you had already. I believe you can get it to work with some adjustments or some clever techniques.

 

 

Good hint,

I forgot that the A* field can be used one for all thousands 

characters, Will try it it seem to be good direction

 

Characters are blocking so indeed i I would need yet some adjustments maybe, not sure if the bigger problem I mean 

this blocking crowd at the end will be resolved though

- if no it still will be not work

 

I was thinking that yet I may tray this go direction if blocked

some randomistaion but maybe do a bit more randomistation 

but more , I mean instead of

-try direct  -if no random  -try direct   -if no random -try direct - if no random 

 

-try direct  -if no random - random - random - random - random -try direct  

 

yet I also need to reapeat "ring1 lowest distance choice" because i doesnt remember how it worked (maybe i was anly doing it with randomistation and forgot to test check the stright way)

 

//EDIT

 

- though ye, it probably will be resolved, I think i can 

generate the distance field each frame (It will eat a few milliseconds though, the map is size about 1000x1000)

so i just can treat all characters as obstacles too

 

as to generatting this field -

 

can I use local approach I mean use a 2d array

of the size of the map and some wandering algoritm that will we wandering through all 13's and set vicinity zeros to 14

- or some other approach with storing this 'distance fronts' in seperate list is needed? 

 

//ADD

besides if some have some more hints, it would be good

to see, This large distance map each frame would slow the things quite heavy - So its worth try probably but maybe is not  optimal if i do not need perfect 'tracking'


Edited by fir, 15 March 2014 - 12:57 PM.


#5 Waterlimon   Crossbones+   -  Reputation: 2565

Like
0Likes
Like

Posted 15 March 2014 - 02:07 PM

Im not sure if you can treat agents as obstacles in the generation (think long pathway blocked by single agent, if you treat it as obstacle other agents at start will find no path to goal since the flood fill never gets past that point)

 

You need something that acknowledges the fact that agents are TEMPORARY obstacles UNLESS clumped at goal in which case they are actual stationary obstacles. Treat agents as obstacles if they are part of the goal clump thingy, otherwise treat them as temporary obstacles that you might be able to just wait until they move out of the way.

 

You can probably achieve this through some cleverness, treating the whole goal agent clump as the goal (so goal is complex area instead of single tile) I think this would work to some extent.


o3o


#6 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 15 March 2014 - 04:22 PM

Im not sure if you can treat agents as obstacles in the generation (think long pathway blocked by single agent, if you treat it as obstacle other agents at start will find no path to goal since the flood fill never gets past that point)

 

 

 

It weel be used for mostly free open area - some like batalistic movements of the large army, As i said i dont need it exact and precise just working mostly (may wonder and slug but should tend to destination mostly ),

 

It should work very good imo for my cases -  worse thing is that calculating this 1000x1000 distance fields each frame would be

a bit heavy 



#7 ApochPiQ   Moderators   -  Reputation: 15765

Like
1Likes
Like

Posted 15 March 2014 - 04:24 PM

A 1000x1000 grid with a few hundred (or even a couple thousand) units should pose no issues on modern hardware if you implemented and optimized A* correctly. Maybe you could post your code for examination?

#8 jefferytitan   Crossbones+   -  Reputation: 2127

Like
0Likes
Like

Posted 15 March 2014 - 04:44 PM

Are all 1000 agents trying to pathfind to the same destination? Is that destination moving? One of the methods I've heard of for many agents going to a single static location is a vector field, basically each cell has a vector indicating which direction to go. The vector field is only calculated once. If you need it to update the destination, you could update the vector field over multiple frames, spreading out from the destination.



#9 dmatter   Crossbones+   -  Reputation: 3101

Like
0Likes
Like

Posted 15 March 2014 - 05:15 PM

You could also consider the potential fields approach. It can suffer from local minima issues when obstacles are introduced (if done naively and allow an obstacle's area of influence overlap with other obstacles'). In a rough sense I see it like it's trying to cheaply create a voronoi diagram of the landscape where your agents follow the edges of the voronoi cells.

 

You could also consider a hybrid approach, start with an A* field and overlay potential fields per agent so that they don't crash into each other and attempt to path around one another without having to run A* per agent.


Edited by dmatter, 15 March 2014 - 05:18 PM.


#10 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 15 March 2014 - 05:15 PM

A 1000x1000 grid with a few hundred (or even a couple thousand) units should pose no issues on modern hardware if you implemented and optimized A* correctly. Maybe you could post your code for examination?

 

 

Are all 1000 agents trying to pathfind to the same destination? Is that destination moving? One of the methods I've heard of for many agents going to a single static location is a vector field, basically each cell has a vector indicating which direction to go. The vector field is only calculated once. If you need it to update the destination, you could update the vector field over multiple frames, spreading out from the destination.

 

destination may be stay in place for many frames but also may be moving very dynamicaly

 

trouble is i want to run it at a very hight frame rates (and for large groups of characters) 

 

so after consideration it seem to me that for this particular case it is limited (could be optymized but to complex ) [very good for other cases like more stable destination]

 

- but I think different simple approach can still be found 

(and this should be not so hard imo)

 

like i said just write some basic 'steering' routines but with improved behavior to change 'some' blocking into ssome go-round trial and that would be all (seem not to be so hard only need a bit of focus and tests)



#11 ferrous   Members   -  Reputation: 2013

Like
0Likes
Like

Posted 15 March 2014 - 08:14 PM

You could just lower the cadence of updates.  Does your all 1000 of your AI really need to get a new path every frame?  A small delay shouldn't be too bad, or too noticeable.  Or conversely, stagger the updates, even something simplistic like, on odd frames do 1-500, even frames do the other 500.



#12 wodinoneeye   Members   -  Reputation: 820

Like
0Likes
Like

Posted 16 March 2014 - 04:00 PM

Are all 1000 agents trying to pathfind to the same destination? Is that destination moving? One of the methods I've heard of for many agents going to a single static location is a vector field, basically each cell has a vector indicating which direction to go. The vector field is only calculated once. If you need it to update the destination, you could update the vector field over multiple frames, spreading out from the destination.

 

Some games have a 'helper' indicator that points the way to go  (like the arrow towards the next player goal which is the correct direction around terrain obstacles... Bioshock for example has this)

The 'cells' are probably the navmesh triangles (simplified from the 3D terrain mesh)

 

Thats an idea -- that possibly (particularly if this is precanend static data and there being some number of them) would be some simplification of any finer 'grid' into a different system to save on memory.  Unfortunately if movement is on the 'grid' then the equivalent of the 'Pick'  (point intesect triangle) would be done to find which 'cell' of the simplified data to use.


Edited by wodinoneeye, 16 March 2014 - 04:03 PM.

--------------------------------------------Ratings are Opinion, not Fact

#13 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 16 March 2014 - 04:47 PM

I made some routine that

- goes in direction of the destination

- if blocked rands the vicinity field that is empty and whose

distance is present characterdistance + 0.3 or any less (0.3 was chosen exparimentaly to allow ranom moves in some sides 

not only forward but not back and not to much on the side)

 

how it works

 

+ it makes close to round group at destination (ok)

+ it doeas only very slight randomization moves by short 

time at the end - where group reaches destination (ok)

(+ it is lightweight method)

 

so two problems were somewhat resolved (I mean i have something close to what i postulated)

 

there ios a third problem yet, when i got a round group of 1000

characters and when i command them to other place it 

began to spread as a some kind of fat line where begin of it is

moving fast but end point stays at place - only where all this

wormlike group unwinds the end began to travel to and whole group is travelling in the form of fat line - I would need to 

change something to make it moving like wkole group (near to round) not soem kind of fat line group - I need to add something 

to allow the group to be more vide (now the rule "less than present ditance + 0.3" prevent it to go wide - becouse more side 

tiles had more distance) But in generel it shows that this simple approach is working - though maybe it is not looking very good

resembling some army movements or something - more like some gum - but is cheap and functional, at least can go round

quickly simple small obstacles



#14 Thorim   Members   -  Reputation: 114

Like
0Likes
Like

Posted 27 March 2014 - 10:42 AM

Hope I can help you somewhat, I am a new to this game programming thing.Just wish I can see a picture of what your current game looks like.

Not exactly sure if actors are tied to tiles (like chess) or a free moving actor (like how most games are). So I will guess you are in a free moving world, also I believe your actors are tied to the pathfinding grid so that is why they make lines. Also the fact you want the actors to form a round shape at the end.

So you want is:

-Fast

-Round group of units at the end

-clam the group at the end

Also I will assume the following:

-1000*1000 grid

-This grid is uniform and stored on a 2D array (important for super duper speed, memory that takes up a 1000*1000 black and white picture)

-simple obstacle

Problem One: Finding a route..fast...superfast

So I see your using A*. Which is great if all the actors are spread all over the place since A* finds all shortest path to one spot. Bad thing is that if you have most of your units in a tight group and is only 200 units away, your A* can look up to 160,000 nodes before finding your group!! My suggestion is create a pathfinding algorithm that can "clump" them together and perform a distance weight pathfinding. Here is my crude pseudocode.

//Frist function

//Finds average position of all your soilders. Also we assume there is magic involved that ignores the troubles if your average lands on top of an obstacle :3

ClumpActors(<actors>ListOfMyArmy,& X,&Y){

Number_Of_Actors=0; //This is just to count the actors as this positions are added

X=0;

Y=0;

iterator<actors> Start = ListOfMyArmy.StartofList(); //this is the frist actor in the list we can use this to grab position data from

while(Start != EndOfActorList){

X=+ Start.GetActorX(); //grab the X and add it to the average

Y=+ Start.GetActorY(); //grab the Y and add it to the average

Number_Of_Actors+=1 //be used later for the great divide to find our average position on the map!!!

}

//Ok now all the actors positions are combined we can now get the average!

X=X/Number_Of_Actors

Y=Y/Number_Of_Actors

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Second function

//Weight base find, very hard to grasp.

//I just made this up, been working all night stocking shelves and had a cup of tea... should work

WeightBasePathFind(PathFindingMap, StartPosition, EndPosition){

//little tricky but this is how it would work, if we have a uniform tile base pathfinding map inside an 2D array

//also note there cannot be any "trap" like rooms if you do add rooms or walls we can use a a different sort of colored map

//to help actors avoid going into such rooms unless the target is in it so it treats the door of the room like a wall and slides right by

//now for the advance and highly complicated algorithm that only a highschool dropout can create

CurrentPosition=StartPosition; //Pass the X and Y over

PathNodeList; //empty pathnode list to store our path!

 X_BestDirection,Y_BestDirection //best directions to choose

enum{ //enums to set different things

UP=1,

DOWN=2,

RIGHT=3,

LEFT=4,

EVEN=5

}

if(CurrentPosition.X<EndPosition.X)  X_BestDirection=RIGHT;  //if your at 0,0 and the target is 5,0 it would be right to you

if(CurrentPosition.X>EndPosition.X)  X_BestDirection=LEFT;

if(CurrentPosition.X==EndPosition.X)  X_BestDirection=EVEN;

if(CurrentPosition.Y<EndPosition.Y)  Y_BestDirection=UP;

if(CurrentPosition.Y>EndPosition.Y)  Y_BestDirection=DOWN;

if(CurrentPosition.Y>EndPosition.Y)  Y_BestDirection=EVEN;

}

****Bunchs of other code but I will stop to let to have fun to figure it out****

The basic Idea is if you have your positon (group mass) lets say at 0,0 and you want to get to the target at 600,600 so you know

that you have to travel UP along the Y axis and RIGHT along the X axis.

To find your way around things is how we humans find routes in real life on streets

-Take a road going to target location

-If road is block take a left turn then on the next available right turn you take it

-Keep track where all your major decisions was (Remember where the road was blocked and you took a Left turn? well it was a dead end so seek back to this spot and this time take a Right turn and look for the next available left turn)

Keep doing that and you find your target (assuming you are not trap inside a concave obstacle so this works on flat walls)

In the code you can also keep track of your last move and treat it as a wall so when you back track to a point on the wall that you took left on you will be forced to take a right, also the cool thing about this code you only have to search one node per frame which is a lot better then have to search though 1,000,000 nodes for each frame >.<

If you do want to tackle harder things like concave objects I would use the pathfinding map you have there and "color" code it really instead on black and white (true/false) to symbolize a path you can walk or not you can have 0 wall 1 open 2 room. A good example if you were in a zombie game and you were chillin in the basement defending against the zombies. Your in a neighborhood and most structures are convex shapes that allows this simple pathfinding for the zombies to seek to the doors of the house your hiding in. When they get to the door, your game does a A* pathfind at your location for all paths in the house to you instead of doing all best paths in the neighborhood to allow your zombies to switch over to a more sophisticated system.

 

OutSide Zombie knows to seek the center of the next best tile closest to you. Slides by house, and concave shape fence attack it until destroyed or climb over it. when at house seek closest door (window,door, blasted hole in the wall) swap over to some other pathfinding to tarhet when enter the "Room Zone", try to kill target.

//////////////////

//////////////////

Problem Two: Rounded group and no waiting lines

Again I am assuming the actors are not really bounded to tiles

I will say we should have the weighted behaviors + state machine

State machine says seek next center of tile but at the same time sets it's next move to avoid being to close to other targets

simple way is take a neighbor and find the normal to it and divide the normal by the length to that actor and add it to a collection vector. Do this to all the neighbors around the actor for a final avoid vector. You will need ways to cut out needless processing for actors to far away, simple sphere test in combination with spatial partitioning, or just spatial partitioning if the tiles are pretty small themselves. Now the State machines don't exactly have to go to the center but only have to get so close before seeking the next tile, keep going until the next tile is EQUAL, EQUAL

 

If you want the group be more groupish and round when they travel then you can a CenterOfMass Seek where all the actors want to be close to it but at the same time want to stay apart. How can might work is you have one point that follows the path to the target while this all the actors only care about the Center of mass instead of the seeking each tile, also you might want to align their headings so that they all point the same way. If they have a normalize vector then you can add all of them up and use that as a seek weight to help align them all. But this will not let them path find well. Solution is to make "Buffers" walls that the Center of mass treats a walls in the path finding map to allow room for the mass the pass around things. For example one tile wall can have 8 "buffer tiles" around it that the center of mass will treat as walls but single actors treat as normal space. When the center of mass gets to the target location all the actors will just chill wiggling about until the next target location. You can have it so the actors will notice that the center of mass is holding still or the center of mass can send a message to all the actors to chill out and will send a new message to follow it again with it goes a new target.

At this point your state machine will switch to STAND_STILL_MODE when it wants to avoid other actors even more so the the ones still seeking the final target can still push the waiters out of the way. The waiters will still look for a fresh target, when a new target is set they will swap to FIND_TARGET_MODE and begin the hunt again!

That should be it, hope it help you or anyone else, also my English is really bad even though it is my primary language.



#15 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 27 March 2014 - 12:52 PM

Hope I can help you somewhat, I am a new to this game programming thing.Just wish I can see a picture of what your current game looks like.
 

 

this is not yet a game this was more a toying with commanding a large (thousands characters at real time) crowd group on large tile map  - could answer later becouse now im doing other thing (prevoius one waoked in a half as i said but i found probably way to improve it i think - instead of counting distance to the destination i could count the amount of blocked tiles on the distance line and move characters to the fields when this kind of distance is low - but yet not tried it

 

(rest i will answer a bit later tomorrow or day after )


Edited by fir, 27 March 2014 - 03:00 PM.


#16 fir   Members   -  Reputation: -460

Like
0Likes
Like

Posted 31 March 2014 - 04:41 AM

 

That should be it, hope it help you or anyone else, also my English is really bad even though it is my primary language.

 

I did not understood that, I got weak english and some kind of narrations are not understandable to me ;/ you also wrote it to long, you could wrote some summery in few sentences , so

i could get at least 30% of idea what do you say [now i dropped 

this massive pathfindigt topic in the state where it half works*,

will return to this later probably yet again to improve this)

 

*as i said if i got a group (and often i got a group becouse in first stage when the soldiers are randomly spreaded then after commanding to direction they are group;  Then after commanding to other direction this is group moving to group

(I mean group movin to another place of the group ;/

 

so this group is moving as a line shape, (like crowded people stopped on the back of others)  the improvement i need would be a group moving more wide like a group of bees - this is to be done probably by this weight-vicinity methods i was talking about but need some efforts etc - will back to this later


Edited by fir, 31 March 2014 - 04:51 AM.


#17 Ashaman73   Crossbones+   -  Reputation: 7517

Like
3Likes
Like

Posted 31 March 2014 - 11:56 PM


So I see your using A*. Which is great if all the actors are spread all over the place since A* finds all shortest path to one spot. Bad thing is that if you have most of your units in a tight group and is only 200 units away, your A* can look up to 160,000 nodes before finding your group!! My suggestion is create a pathfinding algorithm that can "clump" them together and perform a distance weight pathfinding. Here is my crude pseudocode.

There are different solutions for such a problem:

1. Use djiktra to map the shortest path to all grid position only once (Starting point is your group position).

2. Add all units to the open list of A* (goal=grouping point). 

3. Use influence maps (similar to djikstra), you just need to fill the map once.

 

All solutions only need to run once for each group point, regardless of number of units.

 

To solve some kind of clumping together, you could use some simple steering behavior.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS