Dune 2 the maker pathfinding

[Skaldi]

Hello Stefan, I just found out that ur pathfinding doesnt work to 100%.

I would suggest to use the LEE alogorithm.

It works so like in the Garphic I added. (was much work to create :) )

U can also check all 8 fields surrounding the aimfield then u have to prefer the not diagonal fields to drive first, else the tank will dirve zic-zac.

When u chekck 4 fields u have to allow the tank to move 2 indexes and 1 index (for example from 10 to 8). BY the 8 fields you must only allow them to move 1 (from 10 to 9 from 9 to 8, etc...).

And when a field isnt moveable, u dont give a number to it and exclude it from being checked in future. So the algorithm works faster, the more complicated the way is, because it excludes much itself then. On great Areas with no obstacles it works slowest.

With this technik u get the best way to 100%. But u have to code it out proberly cause this technik is very cpu intensive. But it is the only pathfinding algorithm I would use, it is the only 1 which works to 100% and always finds the best way.

It works that way. All Surrouning fields of the aimFiled (which is marked with 0 normally) is marked with 1. All Surrounding fields from 1 are marked with 2, from 2 with 3, etc..., till u reach ur tank.

And never check a field twice, else u will overwirte ist number. And that must not happen.

And at last u drive from the highest number to the lowest.

from 10 to 9 to 8 to 7, etc... till u arrive ur aim.

[attachment archived by Gobalopper]

[XTF]

With this technik u get the best way to 100%. But u have to code it out proberly cause this technik is very cpu intensive. But it is the only pathfinding algorithm I would use, it is the only 1 which works to 100% and always finds the best way.

You should have a look at A*. It's complete and much more efficient.

[Skaldi]

I know A * but it doenst find the way to 100%

[Skaldi]

Okay but a big advantage of the A* is that u can give different movepoints to the floortiles. So u can say a horizontal move to a Betontile costs 10 movepoints, a stonetile 15, a sandtile 20, a dune tile 25 and so on, in that case the tank will drive the quickiest way. Now I am really thinking of it to implement it in my game.

[XTF]

I know A * but it doenst find the way to 100%

Yes, it does, unless you added bugs while implementing it.

[XTF]

I also think you should use 1.4 or 1.5 for diagonal moves, because now, going left and then going down is as 'costly' as going diagonal immediately.

[Skaldi]

Yes thats true but i said for horizontal moves :) .

but taking comma numbers isnt very performant. its better to take costs 10 and 14 for example, that they stay integers.

[stefanhendriks]

actually. I use a mixture between A* and FDS. But i am going to change that into something more 'direct'. At start, i won't be even doing pathfinding at all. Only when the unit encounters something blocking him, he will use the pathfinder. I think that will be sufficient enough for its game type & also taking the amount of 'obstacles' into account.

[neonext]

i use A* and have tried making movement that requires turning cost extra, but havent been able to implement it correctly. so unfortunately my tanks still do that zig-zag movement thing when they are taking short paths (i do long distance pathfinding different, to give less stress to the cpu). Still, overall it works great and is painless for the most part. A* is definitally the right algorithm to use, it just needs to be tweaked to suit your particular game's design and needs

[Skaldi]

A good idea is also to put the units into a movement queue, so lets say only for 5 (may depend on the distance) units a frame the way is calculated and then the next 5 in the next frame etc..., nobody will notice that.

[stefanhendriks]

when your pathfinder is cpu intensive (and it gets more intensive the bigger the map & the further away your goal) then you wont make it with simply queing this.

You could try make it a 'phased' procedure. Ie, you simply want an x amount of cycles in the pathfinder. And you spread it over all units. When 100 units request a path. You simply run the pathfinder for x amount of times. The unit will use a very brute force of movement until it has the 100% correct path.

Its a way. but i don't like it.

I tried several things, and its harder then you might think ;)

[nemafakei]

"I think that will be sufficient enough for its game type & also taking the amount of 'obstacles' into account."

In or around a base, that doesn't work.

Could you not have the unit make a dummy path and then if it finds a fixed obstacle (building, rock), follow both ways around the edges of the obstacle until it finds a way past, then, rather than have the unit hug the obstacle, have it move more directly around it?

[stefanhendriks]

in a base would work ;)

simply it will 'fail' the 1st move and then do what it always is doing. Finding a path around it.

Basicly i am adding a step before doing the 'tough' stuff ;) Calculating  path. It would be a waste of cpu if there would be a straight line possible no? :)

[nemafakei]

So, am I right in thinking that it will only think about it once the unit has run into something?

[stefanhendriks]

yep

[Skaldi]

Hehe you know i always try to do the supermega thing, so I am on a really cool A* using binary heaps and naturally sorted lists. Else I have made an algorithm which puts together 32*32 to 1 tile, and the tiles know which tiles can be reached from it (think thats called quadtree). So u can quickley calc the way, cause 64*64map is then a 2x2map, and 1024*1024 is a 32*32.... And the "finepathfinding" is done in those "little" 32*32 tiles. And so i should be able to move 100 - 150 tank in a 1024*1024 (if needed with movementqueues) without a noticable delay.

[XTF]

Hehe you know i always try to do the supermega thing, so I am on a really cool A* using binary heaps and naturally sorted lists. Else I have made an algorithm which puts together 32*32 to 1 tile, and the tiles know which tiles can be reached from it (think thats called quadtree). So u can quickley calc the way, cause 64*64map is then a 2x2map, and 1024*1024 is a 32*32.... And the "finepathfinding" is done in those "little" 32*32 tiles. And so i should be able to move 100 - 150 tank in a 1024*1024 (if needed with movementqueues) without a noticable delay.

But does it find the optimal route?

[Skaldi]

This method finds "almost" the optimal route, and the object will never drive the wrong way.

Imagine there is a spot surrounded by cliffs, and there is 1 way out in the north. And you click at the south beyond the cliffs. So my Object will naturally dirve directly out by the north. But the optimal way isnt found.

[XTF]

Also, has any of you thought about 'free' paths instead of paths exactly through the centers of cells?

[stefanhendriks]

I am not sure what you mean by that olaf?

[XTF]

I am not sure what you mean by that olaf?

Well, for example, if you'd like to go two cells up, one cell left, can that be done in a straight line?

Or will it require two lines, one horizontal and one diagonal?

[stefanhendriks]

basicly i wonder if it even matters.

My pathfinder tries to do diagonal paths as well. So, basicly it will do:

UP-RIGHT

UP

which is the shortest path.

[XTF]

No, a straight line between the two points is shorter (by 7%). And it doesn't require an extra turn.

[stefanhendriks]

ah you mean like that. No , since the game sticks to its cells. It can't skip them