Dynamic A* Pathfinding 3.2

Advanced game related topics
Chrono Syndrome
Enthusiast
Enthusiast
Posts: 169
Joined: Thu Oct 05, 2006 6:44 am
Contact:

Post by Chrono Syndrome »

Hm... What's about support for custom-shaped units, which occupy more zen 1 cell ?
Don't try to catch ze Night !
Remember: 'z' is better zen 'th' =) !
Sorry for bad english.
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

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...
I love Purebasic.
Chrono Syndrome
Enthusiast
Enthusiast
Posts: 169
Joined: Thu Oct 05, 2006 6:44 am
Contact:

Post by Chrono Syndrome »

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...
Don't try to catch ze Night !
Remember: 'z' is better zen 'th' =) !
Sorry for bad english.
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

Oh, I see what you're saying now.. I'll try to add that in a future version.
I love Purebasic.
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

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.
I love Purebasic.
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

Updated to 2.2

Added support for dynamic objects, ray and more
I love Purebasic.
JCV
Enthusiast
Enthusiast
Posts: 579
Joined: Fri Jun 30, 2006 4:30 pm
Location: Middle East

Post by JCV »

cool. nice work :wink:

[Registered PB User since 2006]
[PureBasic 5.7][SpiderBasic 2.2] [Win 10 64bit]
[Intel i7 990x 4.20 Ghz] [18GB DDR3]
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

JCV wrote:cool. nice work :wink:
Thanks man, doing my best :P


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).
I love Purebasic.
JCV
Enthusiast
Enthusiast
Posts: 579
Joined: Fri Jun 30, 2006 4:30 pm
Location: Middle East

Post by JCV »

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
Image

[Registered PB User since 2006]
[PureBasic 5.7][SpiderBasic 2.2] [Win 10 64bit]
[Intel i7 990x 4.20 Ghz] [18GB DDR3]
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

...
Last edited by Heathen on Fri Dec 28, 2012 10:22 pm, edited 1 time in total.
I love Purebasic.
Heathen
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

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:
I love Purebasic.
Barney
User
User
Posts: 54
Joined: Wed Apr 26, 2006 12:01 pm

Post by Barney »

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
Enthusiast
Enthusiast
Posts: 498
Joined: Tue Sep 27, 2005 6:54 pm
Location: At my pc coding..

Post by Heathen »

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 :P

edit: Increased to microsecond
I love Purebasic.
tmyke
Enthusiast
Enthusiast
Posts: 132
Joined: Fri Sep 29, 2006 1:10 pm
Location: France

Post by tmyke »

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.
:)
Strength and wisdom.
Image
Barney
User
User
Posts: 54
Joined: Wed Apr 26, 2006 12:01 pm

Post by Barney »

New values:

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

(Intel E6600, 2 GB RAM, ATI X1950XTX)

Barney
Post Reply