Hi,
Does anybody know how I can calculate the shortest route in a maze.
In my maze (2D array) walls are represented as a "2". There are monsters in it and they have to take the shortest path to my character without walking into walls.
How shoud I handle this?
Some sort of algorithm?
Greetz Daan
If you are going to do a maze and want to calculate shortest path, you should ditch arrays and look into graphs.
http://www.cs.sunysb.edu/~algorith/files/graph-data-structures-L.gif
each node and edge would have a variable or static weight on it. Depending on where your monster is and the location of the target is, you would do the necessary calculation, and go.
@xiardana:
It's already possible to do that. I used the formula from this site
http://www.mathwarehouse.com/algebra/distance_formula/
But that's something different than finding the shortest path, the formula doesn't take walls in acount and I need something that calculates several routes so I can pick out the shortest route.
@kdajani
I don't quite understand i guess. I also can't reach the image, the site looks down.
Greetz Daan
You can treat your 2d array as a graph by making each element in the array a node, and creating an edge between each adjacent node. If you can only move hor. and vert. in the maze, then your edges will only be between node to the left/right and above/below. If you don't add wall elements to the graph, then they won't be considered as part of the path by the algorithm (they won't exist according as far as the graph is concerned, so they can't be used as part of the path.)
