Author: Aaqid

View the Project

Starting off with the A* The algorithm on an old setup wasn’t my brightest idea. It took me forever to realise I didn’t need to draw every step of the algorithm.

I began by cloning the A* world and refactored it into a class-based structure, anticipating multiple agents on the grid. Using objects from the start seemed the best way to keep things tidy.

After hours of work, the refactor was done; the graphics, path tracing, and visuals all worked perfectly. I thought, “Awesome! I’m a genius.” because the only thing left to be added was an isOccupied variable to handle collisions, but it fell apart! Both agents ended up scanning and rendering at once, causing chaos and overlapping paths. Not what I intended, but the code ran… somehow…it was horrible.

What a letdown! I thought this would be easy. I’d already spent hours debugging but couldn’t figure out the issue. It became clear that sticking to the Ancient Brain A* The setup was a dead end. The worst part? I barely knew p5.js. While I understand game dev concepts but not knowing p5 ‘s syntax made things even more frustrating.

I knew I needed a drastic change, so I decided to start from scratch. First, I had to deeply understand the A* algorithm. I switched to Python with Pygame, a framework I’m comfortable with. I found an old Coding Train live stream where he implemented A* in p5.js. Watching it live gave me a solid grasp of the algorithm. I realised I didn’t need to visualise every step; just the final path was what mattered.

Before diving into coding, I took the time to plan it out. I decided each agent would scan the grid, move if it found a path, then pass the turn to the next agent. This round-robin approach would work even as more agents were added, treating others as obstacles and either moving or waiting.

I ran this plan by the professor the next day. We discussed edge cases in detail, mapping everything out on paper to ensure I had a clear strategy before coding.

I felt confident about this plan: “create an agent with a get_path function using A* to find a path and return it as an array of spots. The agent would then move to the first spot and repaint the canvas.”

Although I had to write the entire Grid and Spot classes, I planned to use The Coding Train’s code as a base, so it seemed manageable. I started rewriting everything, and soon enough, I had a basic grid and a working Agent class that generated a path between spots. Success! I was thrilled.

Core Design

The loop was simple: get the path (an array of spots), then call a function to move the agent to the first spot in the path. If no path was found, the agent wouldn’t move. If there was a valid path, it would take one step; otherwise, it stayed put.

I also added an agent boolean in the Spot class to indicate if a spot was occupied. This helped the A* algorithm check not just for walls but also if another agent was blocking the spot.

So, after all that effort, did it actually work? I needed to verify if A* was treating other agents as walls, so I coloured the spots in the path array blue to visualise the final path returned by the get_path function. I also marked the agent spots in orange for a clearer view of what was happening. Here’s the output.

Awesome! The core algorithm was working and I was really proud of the architecture. It was my own! I used a shared path array where each agent stored its calculated path, which I then used for visualising on the canvas. I also added a function to move the agent one step forward in its path. If no path was found, the agent simply stayed put and passed the turn to the next one.

Next, I wanted to add more agents and make it visually appealing. I downloaded some images; trees, Pac-Man ghosts for the agents, and flags for the destination. It took a bit of trial and error, but most of the effort was just figuring out the correct order to draw each element. Here’s how it turned out.

I was really proud of it at this stage, but there was still more to do. The code was in Python with Pygame, so I needed to port it to p5.js. Plus, I wanted to replace the random walls with streets and roads for a more realistic look. I tackled the conversion first. After a few hours of work, everything was running smoothly, except the images. Despite having transparent backgrounds, they appeared with ugly white edges in p5.js. I solved this by creating custom sprites in Figma, matching the background colour of the streets, which successfully hid the unwanted edges.

After making a lot of tweaks to the code and giving it the look of streets with small houses and trees, I decided to design it with compact blocks resembling actual houses. I got inspired by the typical houses you see here in Ireland, where you often have two or three clusters of homes joined together. That was the main inspiration behind this design choice. I also made sure to change the path colour for each agent, making it easy to visualise where each agent intends to go. Here’s what the world looks like now in p5.js.

Things I am Proud of:

1. Grid Design: The block-based grid system, enhanced with trees, creates a natural, residential look.
2. Core Algorithm: Efficient use of a global path array with a unified function for agent movement aligns well with game dev principles and project requirements.
3. Custom Assets: I created unique assets, solved the white background issue, and added diverse house designs for realism.
4. Colour Palette: Thoughtful selection of colours for assets and paths enhances clarity and is visually pleasing.
5. Incremental Development: Built the project step by step, ensuring each component worked flawlessly before increasing complexity.

A Weird Problem I Encountered

Calling getPath every loop failed, but using it inside an if block worked in both Python and JS. Likely due to how Pygame/p5.js update the canvas. Not sure why, but it now updates and moves correctly.

A Dope Edge Case!

Three agents get stuck in a loop, blocking each other on the recalculated paths. Clip available.

Things That I want to add things that could be better:

1. I originally considered using a cross for symmetry in sideways movement but chose circles instead, as they fit the “agent” vibe, resembling mini UFOs. Now, I want to add rotation functionality so the sprite turns and faces the correct direction (heading).
2. I want to add street dividers to improve map visualisation. To do this, I’ll need to write some logic to decide whether to place them vertically or horizontally, which will take some effort. However, it’s definitely worth it as it will enhance the aesthetics of the map.
3. I want to make the path colour blocks transparent so they don’t cover the Goal Flags, which currently makes it hard to see the destination. Right now, due to how I’m drawing the path, I can’t use the alpha channel because I’m colouring the spot instead of drawing the path over it. This is something I want to improve.

Link to my github repository (python implementation): Visit

Link to my Figma Assets: Visit

Link to The Coding Train Live Stream which helped a lot: Visit

Pathfinding is a fundamental concept in game development and artificial intelligence, helping agents navigate through obstacles efficiently. One of the most widely used algorithms for pathfinding is the A* (A-star) algorithm. In this article, we will break down the getPath function, which implements A* search to find the shortest path between a start node and a destination node.

What is A* Pathfinding?

A* is an informed search algorithm that finds the shortest path from a start node to a destination node using a combination of:

• g-score ( ): The cost to reach the current node from the start node.
• h-score ( ): The heuristic estimate of the cost from the current node to the destination.
• f-score ( ): The total estimated cost (i.e., f = g + h).

The algorithm prioritizes exploring nodes with the lowest f value, ensuring an efficient and optimal path to the goal.

Breaking Down the getPath Function

Step 1: Initialize the Algorithm

this.path = [];
this.openSet = [start];
this.closedSet = [];

Here, the algorithm initializes:

• this.path: An array to store the final path.
• this.openSet: A list of nodes to be evaluated (starting with the start node).
• this.closedSet: A list of nodes that have already been evaluated.

Step 2: Set Up the Starting Node

start.g = 0;
start.h = Grid.heuristic(start, destination);
start.f = start.g + start.h;

• The g-score of the start node is set to 0 (no movement cost yet).
• The h-score is calculated using a heuristic function (Grid.heuristic), estimating the distance from the start node to the destination.
• The f-score is computed as g + h to prioritize nodes.

Step 3: Begin the Main Loop

while (this.openSet.length > 0) {

The algorithm iterates as long as there are nodes left in openSet (meaning there are still nodes to explore).

Step 4: Find the Node with the Lowest f-score

let current = this.openSet[0];
for (let node of this.openSet) {
    if (node.f < current.f) {
        current = node;
    }
}

• The algorithm searches openSet to find the node with the smallest f value, prioritizing nodes that are expected to reach the goal faster.

Step 5: Check If Destination is Reached

if (current === destination) {
    this.path = [];
    while (current) {
        this.path.push(current);
        current = current.previous;
    }
    this.path.reverse();
    return this.path;
}

• If the current node is the destination, the algorithm reconstructs the path by tracing back through the previous references and returns it.
• The path is reversed to present it in the correct order (from start to destination).

Step 6: Move Current Node from openSet to closedSet

this.openSet = this.openSet.filter(s => s !== current);
this.closedSet.push(current);

• The current node is removed from openSet, as it has been processed.
• The current node is added to closedSet, preventing it from being re-evaluated.

Step 7: Process Neighbors

for (let neighbor of current.neighbours) {
    if (!this.closedSet.includes(neighbor) && !neighbor.wall && !neighbor.agent) {

• The algorithm loops through current‘s neighbors, filtering out nodes that are:
  • Already in closedSet (processed nodes).
  • Walls (obstacles).
  • Agents (other entities that may block movement).

Step 8: Calculate g-score and Update Neighbor

let tempG = current.g + 1;
if (!this.openSet.includes(neighbor) || tempG < neighbor.g) {
    neighbor.previous = current;
    neighbor.g = tempG;
    neighbor.h = Grid.heuristic(neighbor, destination);
    neighbor.f = neighbor.g + neighbor.h;

• The g-score is updated for the neighbor (tempG = current.g + 1, assuming uniform cost movement).
• If the neighbor is not in openSetor its g-score improves, it is updated with:
  • previous set to current (for path reconstruction later).
  • Recomputed h and f scores.

Step 9: Add Neighbor to openSet if Necessary

if (!this.openSet.includes(neighbor)) {
    this.openSet.push(neighbor);
}

• If the neighbor was not already in openSet, it is added so it can be considered in future iterations.

Step 10: Return Empty Path if No Solution Found

return [];

• If the loop exits without finding the destination, no valid path exists, and an empty array is returned.

Summary

This implementation of A* pathfinding efficiently finds the shortest path in a grid-based environment by:

1. Initializing the starting node and setting up openSet.
2. Iteratively choosing the node with the lowest f-score.
3. Checking if the goal is reached.
4. Moving nodes from openSet to closedSet to prevent re-evaluation.
5. Updating neighbors’ scores and paths dynamically.
6. Returning the optimal path or an empty array if no path exists.

This method is particularly useful in game AI, robotics, and navigation systems, ensuring intelligent movement across a map while avoiding obstacles efficiently.

Example: https://run.ancientbrain.com/run.php?world=5488323698

Full Code

getPath(start, destination) {
    this.path = [];
    this.openSet = [start];
    this.closedSet = [];

    start.g = 0;
    start.h = Grid.heuristic(start, destination);
    start.f = start.g + start.h;

    while (this.openSet.length > 0) {
        // Finds the node in openSet with the lowest f-score (estimated total cost)
      let current = this.openSet[0]; // Assume the first element has the lowest f-score

        for (let node of this.openSet) {
          if (node.f < current.f) {
            current = node; // Update current if a node with a lower f-score is found
          }
        }
              
      if (current === destination) {
        this.path = [];
        while (current) {
          this.path.push(current);
          current = current.previous;
        }
        this.path.reverse();
        return this.path;
      }

      this.openSet = this.openSet.filter(s => s !== current);
      this.closedSet.push(current);

      for (let neighbor of current.neighbours) {
        if (!this.closedSet.includes(neighbor) && !neighbor.wall && !neighbor.agent) {
          let tempG = current.g + 1;

          if (!this.openSet.includes(neighbor) || tempG < neighbor.g) {
            neighbor.previous = current;
            neighbor.g = tempG;
            neighbor.h = Grid.heuristic(neighbor, destination);
            neighbor.f = neighbor.g + neighbor.h;
            if (!this.openSet.includes(neighbor)) {
              this.openSet.push(neighbor);
            }
          }
        }
      }
    }
    return [];
  }

Credits: TheCodingTrain & AncientBrain

Sahibooo…
Oh Beloved…

Be-ha chaani maayey.
I, In your love…

Emi taap-a kraayey.
like in the sun’s searing rays…

Zaayyi kernas hooo.
Have been withered away.

Sahiboo
Oh Beloved

kyah kar tse ros ba
What do I do without you…

yath lola naaye.
in this boat of love?

Zaayyi kernas hooo.
I have been wasted away.

Sahiboooo, Sahiboooo
My Beloved! Oh My love!

Haa, Zaayyi kernas hooo
O! I am so wasted!

Sahiboooo, Sahiboooo
My Beloved! Oh My love!

Ba-ha chaani maayey.
I, In your love…

Zaayyi kernas hooo
Have been wasted away.

(Sahiboooo… Sahibooooo)
(Beloved.. O Beloved)

Yemi chaani shahrek
In this city of yours

Yemi chaani shahrek
In this city of yours

Lukh chi Vopran chashma wathrawan
people wipe the tears of strangers

Heraan kernas chani jaaye
This place of yours has left me astonished

Zaayi karnus ba
It has wasted me

Zuna gaashi manz
Beneath the moonlight

Zuna gaashi manz
Beneath the moonlight

Yusuf banith chi draakh Dal saaelus.
Draped like Yusuf, You journeyed through Dal Lake,

chi draakh Dal saaelus
You journeyed through Dal Lake

Laaraan pate ches chani tsaayee
I chase after your shadow

Zaayi kerthas ba
You have wasted me

Sahiboooo, Sahiboooo
My Beloved! Oh My love!

Haa, Zaayyi kernas hooo
O! Your love has wasted me

Sahiboooo, Sahiboooo
My Beloved! Oh My love!

Ba-ha chaani maayey
I, In your love…

Zaayyi kernas hooo
Have been wasted away

Reading small text on a screen can sometimes be tricky, especially when working for long hours or dealing with detailed content. Thankfully, Macs come equipped with accessibility features like Display Zoom, which can help make everything on your screen larger and easier to see. In this guide, I’ll walk you through how to turn on Display Zoom in just a few simple steps.

Step 1: Open System Settings

Step 2: Go to Accessibility

Step 3: Go to Zoom

Step 4: Find “Use Scroll Gesture with modifier keys to zoom”

Step 5: Toggle it on

Step 6: Click on “Modifier key for scroll gesture”

Step 7: Set the Modifier key for scroll gesture to ‘Control’

Step 8: Find “Zoom Style”

Step 9: Change it to “Full Screen”

With these simple steps, you can easily enable Display Zoom on your Mac, making it much more comfortable to read and navigate your screen. Whether you’re working, browsing, or just relaxing, this accessibility feature ensures everything is clear and easy to see.

How to use display zoom on a mac?

To zoom in on your Mac screen, simply hold down the Control key and scroll up or down using two fingers on the trackpad (MacBook) or the scroll wheel on your mouse. The entire screen will zoom in, centred around the location of your mouse pointer, making it easier to see fine details.