This is a repost of Rhu’s tutorial originally posted on the MochiAds community forum, so we can share it more broadly with the community. I invite you to read the original article and thread on the forums. –Ada

Ever wondered how people are able to have all their AI walk around walls, water or even other players? Here I will cover one of the many sorting algorithms out there that could manage this, and once you understand it the possibilities are endless!

Introduction:

Ok, so after much thought about what to do next in flash I decided that a wee break from it might be in order, so I’m going to write a tutorial with the hope of educating people on shortest path algorithms, and at the same time hopefully give something back to the Mochi community.

I’ve seen so many flash games make use of them that are simply directly copied off someone else’s tutorial, so a little word of warning: this tutorial will NOT give you any flash code what so ever, I have no intension of educating people who are trigger happy with ctrl+c/ctrl+v. I want you to understand the algorithm, so you can build on it and adapt it to new problems and create some new and interesting never-before-seen games.

There are some truly amazing games out there that make use of shortest path algorithms, probably the most popular being Desktop Tower Defense, and it’s games like these that have inspired me to try and get up-and-coming flash developers to understand some important algorithms.

As stated in the title, this tutorial will cover Dijkstra’s algorithm. Unlike algorithms such as the A* Algorithm (which I will hopefully write a tutorial on later), Dijkstra’s algorithm can compute the shortest paths from a given start point to all other nodes without effecting the runtime – which does have many advantages depending on what you’re programming. Make sure you have a read around google for ’shortest path algorithms’ if you’re unsure about which to use – that or do something outrageous and buy a book :o Don’t run away quite yet though, pictures coming up ;)

Background on Pathfinding Algorithms

:

Shortest path algorithms, for those of you that don’t know, are used to find a path between two vertices such that the weight of the constituent edges chosen are minimised.

Dijkstra’s algorithm, was created by Dutch computer scientist Edsger Dijkstra in 1959.

I think that enough background, I’ve never been a fan of writing huge amounts of text about it :)

Helpful notes on the algorithm we’re about to look at:

s, v, and w are all verticies, with three properties attached to them:

• Known
• Path
• Distance

s is the initial vertex
v is the current vertex being used
w is the current adjacent vertex being used

Algorithm:

Set all verticies as not known, and with infinity distance
Set s.distance to 0
while true
	set v to be the vertex with the smallest distance, that isn't known
	if v is null
		break
	set v.known to true
	for each w adjacent to v
		if w.known is false
			//costVW is the distance from vertex v to vertex w
				if v.distance + costVW < w.distance
					w.distance = v.distance + costVW
					w.path = v

Look a little confusing? Not to worry, I'll try my best to break this down to explain it further with the use of some helpful pictures. Here's the initial graph that we will be applying the Dijkstra's Algorithm to:

As you can see the graph consists of 5 nodes: A, B, C, D and E, and a total of 7 edges: {AB, AD, AC, BD, CD, CE, DE}, all of which have been assigned weights.

There are many different reasons you might want to have different weights between nodes when applied to a flash game. For example, when travelling from point C to point D, there might be water directly between so it will be hard to walk this direct path (a higher weight could reperesent this), so it might be quicker to simply walk around the water. Other reasons could include something as simple as a wall, the weight between C and D could be set so high that the character could never walk this path. I'll let you decide how to apply it to your own work though.

For this example I have chosen that I want to figure out the shortest path to all other nodes from point E, so let's get started.

Table:

Now I hope after looking at all the nice pretty pictures I took the time to draw, that you were making a table to represent the data at the same time? ;) No? Oh well, here you go.:

• K = known
• D = distance
• P = path

This table shows the data after each path, it coincides with the diagram so if you're still not sure about what is going on relook over the diagrams and compare it with the table. For those of you still programming in a procedural way might find this harder and messier to implement than those of you that have took the time to learn an object orient way to programming. Although there's nothing wrong with programming in a procedural way, I find it much easier to keep code all neat, tidy and reusable with an object oriented approach. Don't know what I'm talk about? Wiki it :p

End note:

That about covers what you need to know, I have taken the time to create an example with a table and diagrams, and on top of that provide the algorithm - which more than enough to let you understand Dijkstra's Algorithm. Hopefully I'll have the time to create some other tutorials in a similar fashion to cover all the other great sorting alogirthms out there. If you're stuck trying to implement it then message me through the community, or comment on this post.

Good luck!