Tagged Questions
23
votes
4answers
2k views
Is the Manhattan distance monotonic when used as heuristic function?
I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1.
I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
5
votes
1answer
128 views
trapped inside a Graph : Find paths along edges that do not cross any edges
This is a graph based platformer level and the round shapes are creatures.
I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the ...
