Dynamic A* Pathfinding 3.2

Chrono Syndrome · Post by **Chrono Syndrome** » Thu Jul 12, 2007 8:16 am

Hm... What's about support for custom-shaped units, which occupy more zen 1 cell ?

Heathen · Post by **Heathen** » Thu Jul 12, 2007 5:46 pm

Chrono Syndrome wrote:Hm... What's about support for custom-shaped units, which occupy more zen 1 cell ?

I'm not sure what you mean by that.. You can set the blocked cells to make any shape...

Chrono Syndrome · Post by **Chrono Syndrome** » Fri Jul 13, 2007 9:05 am

Heathen wrote:
Chrono Syndrome wrote:Hm... What's about support for custom-shaped units, which occupy more zen 1 cell ?
I'm not sure what you mean by that.. You can set the blocked cells to make any shape...

Yeah, but we can't find path for someone, who occupy more zen one cell...

Heathen · Post by **Heathen** » Fri Jul 13, 2007 7:23 pm

Oh, I see what you're saying now.. I'll try to add that in a future version.

Heathen · Post by **Heathen** » Mon Jul 16, 2007 4:04 pm

Updated to 2.1.

Now I'm working on a system to compute very large paths. Hopefully it works out..

PS: The reason I'm making every optimization I can find (no matter how small) is because I'm using this in a project where every millisecond counts.

Heathen · Post by **Heathen** » Mon Jul 23, 2007 3:24 am

Updated to 2.2

Added support for dynamic objects, ray and more

JCV · Post by **JCV** » Mon Jul 23, 2007 4:03 am

cool. nice work

Heathen · Post by **Heathen** » Mon Jul 23, 2007 4:15 am

JCV wrote:cool. nice work

Thanks man, doing my best

Todo in next version:

- Optimize ray() procedure a bit (regarding the reallocating)
- See if I can add support for dynamic objects which use a linked list
- Fix problem with ray not taking diagonal blocking into consideration

Future
- Add a threaded callback system for dynamic objects
- System for very large paths (still planning)

Note about the ray:

- Takes diag into account
- Fails as soon as a block is hit (or dynamic object)
- If the ray fails, it will attempt to pathfind instead
- Use your own judgment about this feature. get_path() will always be faster if the ray is successful, if not, it will be slower then not casting a ray (but not by much in most situations).

JCV · Post by **JCV** » Thu Jul 26, 2007 5:39 pm

I've been reading a lot of A* implementations but this topic took my attention today.

Towards realistic pathfinding.
http://www.gamasutra.com/features/20010 ... ter_01.htm

sourcecode and demo
http://www.gamasutra.com/features/20010314/pinter.zip

Using realistic pathfinding will result something like this

Heathen · Post by **Heathen** » Fri Jul 27, 2007 2:27 am

Heathen · Post by **Heathen** » Fri Aug 03, 2007 1:27 am

Updated to 3.0. Lots changed in this update, including a brand new example!

If you test it out, please post the numbers that are drawn on the screen.

FPS:
Validation time:
Path generation time:

Barney · Post by **Barney** » Fri Aug 03, 2007 12:05 pm

FPS: 40/40
Validation time: 0 ms
Path generation time: 0 ms

(Intel E6600, 2 GB RAM, ATI X1950XTX)

I reckon, you should increase timer precision...

Barney

Heathen · Post by **Heathen** » Fri Aug 03, 2007 2:04 pm

Barney wrote:FPS: 40/40
Validation time: 0 ms
Path generation time: 0 ms

(Intel E6600, 2 GB RAM, ATI X1950XTX)

I reckon, you should increase timer precision...

Barney

yeah, was thinking the same

edit: Increased to microsecond

tmyke · Post by **tmyke** » Fri Aug 03, 2007 5:32 pm

on my Pentium IV 640 (3.02Ghz) - 1Mo RAM - NVidia 6800GT 256Mo :
FPS: 12/40
Validation time: 0 ms
Path generation time: 0 ms

on my Pentium M 1.7Ghz - 512Mo RAM - ATI 9700 Pro:
FPS: 15/40
Validation time: 0.108 ms
Path generation time: 0.004 ms

Very good code, I like much and congratulation.

Barney · Post by **Barney** » Fri Aug 03, 2007 11:52 pm

New values:

FPS: 40/40
Validation time: 0.052 ms
Path generation time: 0.003 ms

(Intel E6600, 2 GB RAM, ATI X1950XTX)

Barney