Search code examples
graph-theorydijkstrapath-findinga-star

how do you represent obstacles in a grid for pathfinding as a graph

my program compares A* pathfinding algorithm to dijkstra's algorithm showing how informed searches are better than uninformed. in the write up i explained how a grid is actually a graph with equal distance between noded as such that grid(0,0) and grid(0,1) are nodes, and the moving between them is the edges of the graph.

i also represented it visually.

graph and grid representation

my question is how would you represent an obstacle in graph form? (An obstacle is defined as a grid Position that cannot be traversed.

would it be a) where the node is unreachable

no edges to obstacle node in directed graph

or would it be b) where the directions allow an in but not and out, so it should be avoided?

option be where direction only include a to and not a from

or would it be c) where that node simply does not exist? enter image description here

Solution

  • Suggestions (a) and (c) are exactly the same, with (a) taking a little bit larger memory (depending on how you implement the whole problem and model it as a graph). Suggestion (b) is possible if your use-case needs to report that the current action leads to a sink/error/not-allowed state, so if you just need to compare algorithms then I think it is not necessary to consider it.