top of page

PROGRAMMING PROJECTS

This page contains an overview of four different projects I worked on. Below I have shortcuts to each project, but you can also just scroll through them all.

You can find the files for these projects on my github page: https://github.com/Bobertone

AStar Pathfinding Unity Follow Cam.gif
BoidTrailTornadoShort.gif

MINIMAX CHESS BOT

April 2024   |   Solo Project   |   Programmer

​​This project was made for an assignment for my Advanced Game AI class. I created two different bots to play chess, one that is greedy and shortsighted and one that uses minimax. These bots ran in a chess program that was provided by my professor, so the logic for moving pieces and capturing was already done.​

​​​​​​​​

The bots both operate on a system wherein each piece is given a value, and they try to maximize the net value of each turn by trying to capture the most pieces and lose the least.

​

The first bot I made uses this system to evaluate every possible move it can make on the board, and then making the best move. I call it the greedy bot. This simple strategy is pretty effective, and will actually beat a lot of players and even other bots. In the first gif on the left, I show this greedy bot going up against a bot that just makes random moves.​​

​

The minimax bot  is smarter than the greedy bot because it looks multiple turns into the future to see possible outcomes and chooses the best move based on those options. You can imagine all the possible move choices on a tree, with each choices breaking off into a new branch. The depth of how many moves the bot looks into the future is configurable. For my bot I just have it look 3 moves ahead. The minimax algorithm will track what outcomes have the highest net value and which have the lowest net value, and take turns maximizing and minimizing the value of a choice to simulate itself and the opponent taking the best possible moves. With this logic, even if there is a possible really high value outcome, the minimax algorithm will not make that move because it will recognize that it will be giving an advantage to the opponent in the future.

​

One shortcoming both bots have is that I did not take the time to program heuristics to deal with checkmating, so these matches will usually end in stalemate with just the opposing king left. Doing such would take more time and was outside the scope of the timeframe I had when working on the project.

3 matches of the greedy bot (black) beating the random bot (white)

image.png

a figure to help visualize the minimax algorithm. (Wikipedia, Minimax)

3 matches of the min max bot (black) beating the greedy bot (white)

OCTREES &
A* PATHFINDING

March 2024  |   Solo Project   |   Programmer

​​This project was made for an assignment for my Advanced Game AI class, and consists of two parts. First, I made a method for spatial quantization, the octree. Then I implemented the A* pathfinding algorithm to traverse nodes in the octree. I made this project in Unity.

 

The purpose of an octree is to represent continuous space in a quantified space by splitting the space into 8 child nodes. Those child nodes will then check if there is an obstacle object within their bounds, and if there is, it will create 8 more nodes that are its child. These child nodes will not be created if they would be fully inside an obstacle object. This continues to an extent specified by the user, until the space around obstacle objects has a high level of fidelity in its subdivisions.

​

Then, I use A* to make a pathway from one point to another, using the corners of the quadtree as nodes for traversal. I first find the closest neighbors of each corner node. In a typical grid based A*, these would be like the tiles that border one another. 

​

A* works by calculating 3 values for nodes

  • G cost: the distance from the starting node

  • H cost: the distance from the end node

  • F cost: G cost + H cost

Put simply, A* will go to the node with the lowest H​ cost in the list of neighbors to the start node, and add it to a priority queue and note the node taken to get to that node. The neighbors to the new node will be added to the frontier, a growing list of nodes that can be visited that started with the starting node's neighbors. As nodes are visited, they are removed from the frontier and marked as visited. Usually the algorithm will backtrack to a older node that had a neighbor with a lower F cost than the neighbors available to the most recently visited node. When A* eventually gets to the goal node, it will be able to yield the most efficient path to a goal by recalling the last node they took to get to where they are, one node at a time.

Screenshot (800)_edited.jpg
Screenshot (818).png

WAVE FUNCTION COLLAPSE GENERATION

February 2024   |   Solo Project   |   Programmer

​​This project was made for an assignment for my Advanced Game AI class. I used wave function collapse generation to generate a screen of tiles that followed a logic of which tiles could be next to which. I made this project in Unity.​​​

​

Wave function collapse describes a method of procedural generation where each piece of a group of tiles is generated piece by piece.

​

First, an empty tile is assigned a random value. Then, its neighbors are updated with what values they could possibly be considering the value of that last chosen tile. Then, one of those neighbors is assigned a value from the list of possible values, and the cycle repeats until the group of tiles is finished generating.

WFC_GB_Gen_1c.PNG

3D BOIDS

December 2023   |   Solo Project   |   Programmer

​​This project was made for an assignment for my Game AI class. I implemented a set of rules to generate forces to keep game objects to move together in flocks. These flocking objects are known as "boids" (bird-oid object). I made this project in Unity.​

​​​​​​​

A boid's behavior is comprised of 3 core force calculations: cohesion, separation, and alignment.

  • Cohesion is the force that keeps pulls a boid towards the center of mass of nearby boids.

  • Separation is the force that pushes nearby boids away from each other. This typically happens at a shorter distance than cohesion.

  • Alignment keeps a boid moving in the same direction by applying a force vector with the same direction equal to the average direction vector of nearby boids.

 

An extra fourth force that isn't required is an avoidance force. This keeps boids from running into nearby obstacles. In my case, I have each boid look for the closest position of an obstacle, and apply a force going away from that point based on the boid's distance from that point on the obstacle.

bottom of page