Artificial intelligence has always interested me. Granted, the beginnings of my foray into pathfinding algorithms doesn’t surpass the tip of the great iceburg of artificial intelligence – in fact, it is more akin to an ice cube floating in a vast, slushy sea of knowledge – but this foray and its implications are important enough that I have chosen to document my findings here.
Pathfinding is a very small bay in the aforementioned vast sea that is artificial intelligence. The purpose of many of the algorithms is to find, as the name implies, the path from here to there in the most spatially and temporally efficient manner possible. Oftentimes it is not possible to be both spatially efficient, i.e. finding the shortest path, and temporally efficient – small big-O complexity.
To start this learning adventure, I decided to code up a quick little application in C# to test basic straight-line pathfinding using a queue of waypoints. This is extremely simple from a programming standpoint, and hardly uses any “artificial intelligence” whatsoever. It is significant in that it provides the basic framework that I can expand upon easily for more complicated algorithms.
Consider two points in the plane. The shortest path between those two points is a vector – let’s call it v. This vector is, inherently, a straight line connecting those two points. The simplest way to calculate this vector is to simply subtract the two points. E.g., in the following figure, the vector v that happens to connect the points a and b is defined as [4-1, 5-2] = [3, 3].
What purpose does this vector serve? It can be used as a guide to get from point a to point b. Consider any sort of animation framework. It consists of a series of still images being cycled rapidly (commonly between 30 and 60 frames per second) to create the illusion of motion. Thus, to cause a unit at a to move to b, we simply add v to the position of the unit (a, which is also a vector, as any math professor would argue).
a[1, 2] + v[3, 3] = b[4, 5].
The only problem is that this move is done in one frame. It wouldn’t be a very enjoyable gaming experience if the enemy could instantly move to you no matter how far they happen to be from you. Thus, we need to “slow down” the movement over a series of frames. To accomplish this, we first normalize v by dividing it by its length. To be mathematically accurate, we must find the dot product of v and the reciprocal of its length, since vector division does not exist.
L = sqrt(3^2 + 3^2)
= sqrt( 18 )
v · (1/L) = [3, 3] · (1 / 4.24)
= [3 * (1 / 4.24), 3 * (1 / 4.24)]
= [0.71, 0.71].
Once the vector has been normalized, it can be scaled to whatever velocity the circumstances require by multiplying it by the necessary velocity scalar. For example, 4 pixels of movement per frame:
4v = [0.71*4, 0.71*4]
= [2.84, 2.84]
(total displacement is the length of 4v, or 4.01 – accuracy lost due to rounding to the hundredths place)
Each frame, the unit must update and move at a velocity of 2.84 pixels in the x and y directions, thereby moving at a constant 4 pixels per frame, reaching b in (theoretically) 0.75 frames. Of course, in application, the calculations are all mapped to integer values for individual pixels, and as such, accuracy is lost. The overall effect of this loss of accuracy is negligible in many instances.
Thus, finding the shortest path between two points (in two dimensions) is a very simple matter when there are no obstacles. The most difficult part, though not difficult in comparison to other problems in graphics programming, is getting the unit to behave properly and within the design specifications.
A zip file containing the program demonstrating straight-line pathfinding without obstacles can be found here. It uses a queue of waypoints that are navigated in order. Simply right click to add a waypoint, and the squido guy will “find” his way to it. You’ll need both .NET framework updates (1.1, 2.0) and the XNA framework, which requires at least XP SP2.