Find Shortest Path in Construct 2 & 3
Why shortest path?
You choose shortest path always! When you walk, drive, search or everything else. Your brain wants only fastest way to do a job. It wants a longer one just when you’re meeting your crush! In this tutorial I’m gonna show you how to find the shortest path between two object in Construct 2 & 3, Hope this helps you to develop best HTML5 games.
What is shortest path?
When you’re talking about path, you should imagine a path of points. Like an urban route. When walking in a city your route includes some intersections and squares that are connected to each other through streets.
OK! Until now you have realized that we’re living in a graph and every day we should find a short route to our destination. We know every square or intersection has one or more neighbors that is connected them through a street. Each of those has a name and we know its name and neighbors. This means we have a table in our mind that holds this information.
Which games use this?
I don’t know all games which need to find shortest path but I can say some below:
- Match 4+ developed by ALELADE STUDIO.
- Color Combo developed by osa.studio.
- This can be filled by your next game. Be sure to tell me when you made that.
Dive into the Construct
Practically in Construct game engine I consider every point as a sprite (that is called hexagon) and its neighborhood as overlap or collision
I saved information about every hexagon in its “neighbors” instance variable. But I needed a function to do that. It’s time to introduce my first function: “setHexagonNeighbors ()”.
Breadth First Search (BFS) algorithm
And now we wanna find shortest path between two desired hexagons. But how? The answer is simple and funny! Breadth First Search (BFS) algorithm, one of the most famous algorithms in graph routing. You can find everything about BFS algorithm there.
How does my BFS work?
1.First jobs after touch
Everything begins from source (first) hexagon! Once you touch a hexagon, “source” variable sets to the hexagon UID:
And when you touch another hexagon (as “destination”):
The “findPath ()” function starts the process:
This function sets “path” variable with “source” value as the first parameter, and calls next function.
2.Walking along “path”
When “findPath ()” calls “pop ()” function, it selects and removes first UID from “path”, and sets “processingHexa” to the UID.
Now we know the hexagon that we should find its neighbors is the ”processingHexa”. You can see “pop ()” function below:
At last action of the “pop ()” function, I call another function “pushNotVisitedNeighbors ()”.
I seem to have a lot to explain J. I start with “found”, this variable sets to 1 when we reach to destination hexagon. While that equals 0 and “neighbors” instance variable of processing hexagon isn’t empty “pushNotVisitedNeighbors ()” will do many other jobs.
If “neighbors” variable of processing hexagon is empty (has no neighbors), the function takes us to “pop ()” function (to process next hexagon in the “path”). Else “pushNotVisitedNeighbors ()” scrolls all the hexagon neighbors.
For each neighbor, the function checks out its “distance” variable, if its value equals -1 means it’s a new (not visited) neighbor and should be queued in the “path” , also its “prevHexa” variable sets to “processingHexa” for finding shortest path members at the end, else this shows us the neighbor is already visited and how far we are from the “source”. We’ve nothing to do with a visited neighbor because that has been discovered in a shorter way.
On the next line, the function compares neighbor UID with “destination” variable, and if it doesn’t match, the job is still going on, otherwise calls “setTheShortestPath ()” to find “shortestPath” members.
4.Shortest path members
Congratulations! You’re in the final steps. We’ve done many jobs, set many variables, called many functions and checked out many conditions. Now it’s time to fill out “shortestPath” string with “setTheShortestPath ()”.
OK! Our job is easy here. Just start from the “destination” hexagon and based on “prevHexa” walk along the shortest path toward the “source”, remember when you see a hexagon save its name in “shortestPath”. At the end give “highlightTheShortestPath ()” everything!
5.Lighting the shortest path
I developed this solution based on my own point of view on BFS algorithm, and have no claim to be the best. I’ll be very happy if you leave a comment or optimize my solution and send us via email. You can find everything about BFS algorithm there.