We welcome the ascension of our artificial overlords!

Had a bout of apathy and cynicism for 2025's job market and my own future. Oddly enough, they go away by morning dawn.

To bring our game's NPCs to life, we need to implement movement and navigation logic that allows them to traverse the map and reach their desired destinations. To perform the above, we can build a basic movement system that enables NPCs to move towards a specified goal location on the map, as well as a pathfinding algorithm to determine the shortest path between them and the player's position.

Making NPCs walk across tiles

The tutorial's NPC movement method starts with telling the NPC where our player character is at. Next, the NPC calculates the direction from which it is closest to the player. Then, the NPC finalizes the shortest path to the player. Finally, the wall collision method that handles general movement – while simulating collision via if statements – is fetched at the end.

Our NPC class has its own same-named variable that describes its size, which replaces the player scale variable.

Back to the NPC logic handling method, since we completed the NPC movement method, we might as well animate its movement of chasing the player at the moment.

Look how much your fellow character wants to get close to you…

Building an NPC path navigation algorithm

Re-examining the current iteration of the NPC chasing method, it is a primitive system that brute-edges over walls between the NPC and the player. Mainstream games' enemies have a navigation system that let them patrol across the map to find the player once spotted.

In our game environment, the NPC can move across the map in 8 directions. The tutorial proposes translating them into tuples stored inside a graph they call self.ways that will prove essential in building our pathfinding system.

As we already observed and discussed many times on the 2D debug screen, the game map is a dictionary of tiles (0) and walls (>=1). The graph mentioned in the last paragraph provides the navigational foundations needed for the program to chart the shortest path between the NPC and player's coordinates.

Our pathfinding algorithm then has to loop through self.ways and add any tuples that are not walls into the graph dictionary.

The name of the tutorial's pathfinding algorithm is the Breadth-first search (BFS), which is traditionally an algorithm for searching a tree data structure for a node that satisfies a given property. Our BFS differs from the original model in:

• Data Structure: in a traditional BFS, the data structure is a tree where each node has a fixed number of children. Our game's data structure is a graph, where each node (tile) can have multiple neighbors (adjacent tiles).

• Node Structure: each node in a traditional BFS typically has an explicit structure (e.g., a node object with properties). In our game, the nodes are implicitly represented by their coordinates (x, y) in the game map.

• Different Goals: the goal of a traditional BFS is to find a specific node that satisfies a given property. In this game, our BFS' goal is to find the shortest path between two points (NPC and player coordinates) on the graph.

This iteration of BFS first scans all nodes (tiles) adjacent to each NPC's origin tile (first square ring), secondly that neighbors of the tiles in the first square ring (second square ring), and so on until the goal is found (fourth square ring).

To prevent repetitive scans, the method will store each passing node into a visit dictionary. For each next node that the program will scan, if it is not in the dictionary from earlier, add it to the end of the deque, and set it as the current node.

To get the closest node path to the goal, the program does the following:

1. Get node ring coordinates from BFS method.

2. Initialize an empty list to store nodes that make up the shortest path from start to goal.

3. Retrieve the predecessor node of the goal node. If not found, the start node is returned to a default value. Otherwise, the predecessor node is stored in the step variable.

4. Until there are no more steps, or the start node is equal to the goal node:

   1. Add the current step node to the path list.

   2. Retrieve the predecessor node of the current step node from the visit dictionary and store it into the step variable.

5. Return the last node in the path list, which represents the next steps in the shortest path from the start to goal node. This method does NOT return the entire path.

After you import the pathfinding class into the main file, head to the NPC file.

You can run but you can't hide no more!

Bonus: inter-NPC collisions

Our current iteration of the pathfinding method does not take the sizes of NPCs into consideration, allowing multiple instances of them to potentially overlap with one another while chasing the player.

A quick hotfix by the tutorial suggests using the path variables to control the NPC class's movement method.

The new component needed for preventing NPC overlapping is a dictionary of all living NPCs' map positions.

Referencing each NPC's map positions, neither instance will be able to move so long as their next tile position would be equal to an NPC's tile position.

This iteration does not actually eliminate the overlap feature, merely hide it behind halted movements, it at least prevents multiple NPCs on the same path from colliding with one another so blatantly.