Pathfinding & collisions

[Leif]

Good day.
I have a question about how to realize pathfinding & collisions.

We have a maze (array N x M squares, in which 0- free area, 1 - wall, cannot pass thru). And we have number(about 20 ) of objects, anyone moves from his own start square to own finish square.
Task is:
1.every object must determine his route from square to square from start to finish.
2. When one object collides with another, both of them must recalculate routes considering new obstacle.

How to do it ?

Standard procedure MOVE TO allows to avoid only one type of obstacles ( walls ), and also FPS greatly decreases when using it .
Does anybody use mathematical solution ?

[DST]

Oh man, you just opened pandoras box!

A* pathfinding is the superior way, but its a bit complex. First you make 2 d array (which we'll use in 1d). Whatever grids you use, they should be 1 dimensional, because 2 arrays is twice as much translating to do between arrays.

for this example i'll use 32 x 32 gridsize on 640 x480 resolution, for a grid of 300 in total size.

grid[300][3]; //for grid, this is a global array
path[100]; //to store the path.

so the actor is in grid x, and he checks all nine grids around him, filling in their values.

value 1: parent grid cell (one search started from)
value 2: round(distance(x, y, cell.x, cell.y)); //distance from parent cell
value 3: round(distance(cell.x, cell.y, targetcell.x, targetcell.y)); //distance to destination

now whichever one has the lowest (value2+value3) becomes the next parent cell, so add that cell number to the path[] array. Then we start at that new cell and check all of them again, only this time, if a cell already has a parent id(value1), we ignore it, because it's already been searched.

Eventually, you will end up with a path[] array full of all the cells that have the lowest values. You then wipe all the values from the grid array, so the next actor can use them. After wiping the array, you copy your object values to that array again, under the 'parent' cell, so anything with a box in it will have a parent of 1 and will not be checked.

The trick is that you simply only let one actor do this at a time, to avoid overloading the cpu, although no matter what you do, this is going to be very cpu intensive. Such is the way of pathfinding. One method to avoid the overload has been to use troop formation, where one actor is defined as the leader, he finds the path, and the others just find the path to him. (or rather, they 'flock' to him).

And note that this is only one method, there are many other methods too....

[makslane]

The Move To action with the avoid option uses the A* pathfinding algorithm!

[DST]

Well that means that creating your own like i'm showing is going to be EVEN SLOWER. Just accept A* for what it is.....a resource hog!

Mak, do you have any examples of how it should be used? In reality, you're the only one who truly understands how game editor is supposed to be used.

Most of us have issues with moveto avoid, but i'm sure there's something we're missing.....

[makslane]

Look here:
viewtopic.php?f=6&t=5190

What kind of problem you have?

[DST]

Standard procedure MOVE TO allows to avoid only one type of obstacles ( walls ), and also FPS greatly decreases when using it .
Does anybody use mathematical solution ?

The main problem i think is that it can only be used to avoid one type of object.

We can use a tiled maze, and that's our one object. So how can we avoid both the walls AND other actors standing in our way?

[Leif]

I think in MOVE TO main reason of FPS decreasing is that program determines route considering all the pixels of all the obstacles (very large array) . So if we will work with small one - can it help?
And problem with "one-object-avoid" stays on.