Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Dwachs]

Edit: should have done forum search

here are older threads about the same issue:

http://www.bay12forums.com/smf/index.php?topic=92732.0
http://www.bay12forums.com/smf/index.php?topic=76278.0

can be locked

What is the right place to bring attention to this (not so new anymore) pathfinding method?

Some references first:
http://en.wikipedia.org/wiki/Jump_point_search
https://harablog.wordpress.com/2011/09/07/jump-point-search/ (Blog of one of the inventors)

Jump point search is a modification to A* to prune the search tree. It is effective for large equal-cost areas (in df: large open space on one z-level with same traffic-cost designation), as with this modification less tiles are put into the open list.

I implemented this in an open-source game ( http://www.simutrans.com/en/ ). The implementation was almost trivial, like 5 additional lines to the original path finder. It helped alot to improve performance for some pathfinding tasks.

I heard on the forum that df uses a modified A* pathfinding algorithm. Does anybody know what these modifications are? Does Toady already included this modification?

[RoaryStar]

This is the interview where Toady explained how the algorithm was modified.

[Dwachs]

was there ever a reaction on this jump-point suggestion?