Battleplans: Pathfinding (part 1)
Recently, I've been trying my hand at game development. The goal is to make a classic RTS but with minimal graphics, I am sticking to geometric shapes because I couldn't make things look nice to save myself. Using common lisp and cl-raylib I managed to cover quite a bit of ground quite fast. I am at the point where I can render circles that represent units and rectangles that represent buildings. Centering the text in either of those was more mental gymnastics than I thought it would be, but still easier than CSS.
Pathfinding in dynamic environments
In RTS games the field constantly changes, whether that is new buildings being added, new units created or just them moving around, there really isn't much that is constant. Pathfinding was never a light topic but a dynamic environment along with the constraint to solve those problems in real-time for the game to be playable makes it especially challenging.
The first problem I had here was changing my perception of space. If I want to apply an off-the-shelf pathfinding algorithm I could not be thinking about continuous space, it's all about graphs in that domain... It took me a while to internalize that essentially everything is placed on an imaginary grid, treated like a graph where the value of each slot in the grid was the cost to traverse it. The catch here is that things don't magically teleport from one square to the other, they can be "in-transit", which does create just as many problems as it solves. One thing at a time though.
A*
I decided that having something to build around and use it to understand the problem would be better than nothing. A simple A* implementation should get things rolling. It didn't take much to get it working and even handled cases where there was no path between the unit and the destination which is great.
The point of A* is to not map out the entire grid and assign values, it always picks up searching from the square closest (by manhattan distance) to the goal. Regardless of how big the grid is, the cost only scales by the distance between the start and the goal. At this point I have zero clue how granular the grid should be so I am just winging it and making up numbers, to be adjusted later.
Well, a couple of issues are already apparent. By mapping out just one path, the moment at least one square on that path changes it becomes useless and we need a new one... We really cannot afford to be doing this for every change. We would also need a path per unit, if we wanted 100 units to move at once, that's 100 A* calls, ouch! Lastly, A* would not be able to handle multiple goals. This is important for positioning and targeting. If 2 targets (or more!) are available to a unit then we'd need to get it to pick the closest one and navigate there.
Dijkstra Maps
Since I now knew what was missing, all I had to do was look for it. Dijkstra maps turned out to be a wonderful and very simple tool. It's a terrible name though so I prefer to call them behavior maps. The idea here is that we create a second grid, naming it behavior grid, and on that we mark with 0 all the goals for a unit, or group of them. All adjacent squares are marked as 1, their adjacents 2 and so on. This should take a bit longer to calculate than A* but now, no matter where something is on the grid, if it were to always move to the next square with the lowest number, it would reach one of the goals. Effectively, we have pathfinding for all units, immediately, to all goals.
| 4 | 4 | 4 | 4 |
| 3 | # | 3 | 3 |
| 2 | # | 2 | 2 |
| 2 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 2 | 1 | 1 | 1 |
Where # means blocked
Due to how the behavior map is laid out, a unit will always gravitate towards the closest goal. More than that, the behavior grid is quite easy to manipulate, even if at the first pass we need to map out everything, we can accommodate smaller changes by "patching" it. New building got placed? Let me just mark those squares as closed and adjust the numbers on the adjacent one, done!
This is more than pathfinding though because you can encode all sorts of behavior on that map depending on what a unit needs to do. If it's a passive unit that needs to flee from enemies, or a ranged unit that needs to be X squares away from the target, all of that can be encoded there. It doesn't directly handle the issue with multiple units having to not step on each other but that is something that can be handled at a different level.
The implementation for it is quite clean and simple, nothing fancy though I have not bothered optimizing it yet. My guess is that this is a very SIMD-able problem and maybe I can get a massive speedup that way.
(defstruct (behavior (:constructor %make-behavior))
grid
width
height
goals)
(defstruct goal
(coords (error "No COORDS supplied for goal!") :type vec2)
(priority (error "No PRIORITY supplied for goal!") :type fixnum))
(defun make-behavior (field goals)
(%make-behavior :grid (populate-behavior-grid field goals)
:width (field-width field)
:height (field-height field)
:goals goals))
(defun out-of-bounds-p (x y width height)
(not (and (<= 0 x (1- width))
(<= 0 y (1- height)))))
(defun neighbors (center width height)
(loop for direction in (list (vec 0 1)
(vec 1 0)
(vec 1 1)
(vec 0 -1)
(vec -1 0)
(vec -1 -1)
(vec -1 1)
(vec 1 -1))
for coord = (v+ center direction)
unless (out-of-bounds-p (vx coord) (vy coord) width height)
collect coord))
(defun populate-behavior-grid (field goals)
(let* ((width (field-width field))
(height (field-height field))
(behavior (make-array (list (field-width field)
(field-height field))
:initial-element (1+ (max width height))))
(grid (field-grid field))
(queue (make-queue)))
(dolist (goal goals)
(enqueue goal queue))
(loop for goal = (dequeue queue)
for coords = (goal-coords goal)
for x = (truncate (vx coords))
for y = (truncate (vy coords))
for priority = (goal-priority goal)
unless (or (<= (aref behavior x y) priority)
(eql (aref grid x y) +occupied+))
do (let ((new-priority (1+ priority)))
(setf (aref behavior x y) priority)
(dolist (neighbor (neighbors coords width height))
(enqueue (make-goal :coords neighbor
:priority new-priority)
queue)))
until (queue-empty-p queue))
behavior))
(defun find-closest-neighbor (coords behavior)
(let ((grid (behavior-grid behavior))
(width (behavior-width behavior))
(height (behavior-height behavior)))
(loop with min = coords
with min-value = (aref grid
(truncate (vx min))
(truncate (vy min)))
for neighbor in (neighbors coords width height)
for value = (aref grid
(truncate (vx neighbor))
(truncate (vy neighbor)))
when (< value min-value)
do (setf min neighbor
min-value value)
finally (return min))))
and here is what the unit actually does:
(defvar *units* nil)
(defparameter *unit-size* 16.0)
(defparameter *unit-font-size* 12)
(defstruct (unit (:constructor %make-unit))
(kind (error "KIND not supplied for unit!") :type keyword)
(coords (error "COORDS not supplied for unit!") :type vec2)
(owner (error "OWNER not supplied for unit!") :type player)
(speed (error "SPEED not supplied for unit!") :type single-float)
(behavior nil :type (or null behavior)))
(defun make-unit (&key kind coords owner (field *field*))
(let ((unit (%make-unit :kind kind
:coords coords
:speed 0.5
:owner owner)))
(push unit *units*)
(place unit field)
unit))
(defun move (unit offset field)
(let ((new-coords (v+ (unit-coords unit) offset)))
(unless (or (out-of-bounds-p (vx new-coords) (vy new-coords)
(field-width field) (field-height field))
(occupied-p (vx new-coords) (vy new-coords) field))
(setf (unit-coords unit) new-coords)
(place unit field))
unit))
(defun offset (unit source target)
(let* ((speed (unit-speed unit))
(distance (v- target source))
(x (vx distance))
(y (vy distance)))
(vec (if (minusp x)
(max (- speed) x)
(min speed x))
(if (minusp y)
(max (- speed) y)
(min speed y)))))
(defmethod act ((unit unit) (field field))
(when-let (behavior (unit-behavior unit))
(let* ((normalized-coords (v/ (unit-coords unit) 8.0))
(target (find-closest-neighbor normalized-coords behavior)))
(if (v/= normalized-coords target)
(move unit (offset unit normalized-coords target) field)
(setf (unit-behavior unit) nil)))))
In the future this will probably get a bit more convoluted as I would like to be able to pass in a function that will better define the behavior of a unit but as a starting point, I am really happy with how simple it was to get this working.
Nothing interesting to show at this point but I am having fun, once I get those dumb units to stop running on top of each other I will try and share a video in a following post, along with other problems that came up along the way!