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.

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

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.

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 )

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