Advertisement Jump to content
Sign in to follow this  
fir

massive pathfinding

This topic is 1529 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!