search

b3dgs / lionengine

Java 2D Game Engine
http://lionengine.b3dgs.com
GNU General Public License v3.0
139 stars 23 forks source link

Fix pathfinding algorithm #586

Closed SomeFire closed 5 years ago

SomeFire commented 5 years ago

Expected Behavior

Unit moves in a straight line (shortest way).

Actual Behavior

Often unit moves in a curve line. Sample:

10,9 <- 6,12
Node{x=10, y=9, depth=7, cost=7.0, heuristic=0.0}
Node{x=11, y=10, depth=6, cost=6.0, heuristic=1.4142135623730951}
Node{x=11, y=11, depth=5, cost=5.0, heuristic=2.23606797749979}
Node{x=10, y=10, depth=4, cost=4.0, heuristic=1.0}
Node{x=9, y=11, depth=3, cost=3.0, heuristic=2.23606797749979}
Node{x=8, y=10, depth=2, cost=2.0, heuristic=2.23606797749979}
Node{x=7, y=11, depth=1, cost=1.0, heuristic=3.605551275463989}
Node{x=6, y=12, depth=0, cost=0.0, heuristic=0.0}

Steps to Reproduce the Problem

Just move single unit.

Specifications

SomeFire commented 5 years ago

The main problem is in the TreeSet class, which doesn't check equality, but compares only. So, it can't hold nodes with different coordinates, but equal cost+heuristic together.