Pathfinding Algorithm
The program determines a route from the start cell to the end cell by repeatedly choosing the best next move, tracking visited cells, and backtracking when a path reaches a dead end.
Coding Projects · Data Structures
Frog Pathfinding
A CS1027 Java project at Western where I implemented pathfinding logic for a frog moving across a hex-based pond.
Overview
Help Freddy cross the pond
This project was created for CS1027, Computer Science Fundamentals II, at Western University. The assignment was based around Freddy the Frog, who has to move across a hexagonal pond from a starting cell to an ending cell while avoiding hazards and choosing the best available path.
The pond contains different cell types, including water, lilypads, reeds, flies, mud, alligators, a start cell, and an end cell. Each type affects how Freddy can move. For example, mud cannot be entered, alligators make nearby cells dangerous, reeds can provide protection, and fly cells are more desirable because Freddy can collect flies while moving.
Design approach
The main challenge was implementing the movement logic behind the game board. Freddy does not simply move randomly; he chooses the best next cell based on priority values, nearby hazards, cell type, and whether he is able to jump farther from a lilypad. I used a stack to track Freddy’s current path and a unique priority queue to rank possible next moves. The algorithm had to support backtracking, meaning Freddy could return to previous cells if a chosen path did not lead to the end.
Project Screenshots
Different pond layouts showing pathfinding, movement options, hazards, flies, lilypads, and custom stage data.
What the Project Included
Unique Priority Queue
Possible moves are ranked using a priority queue so Freddy can choose cells based on their type, distance, safety, and usefulness. Lower priority values represent better movement choices.
Custom Pond Files
Stages are loaded from text files, allowing different pond layouts to be created and tested without changing the main program code.
Why it stuck
Data structures you can watch work
This project helped me better understand data structures in a practical setting. Instead of only learning about stacks and priority queues in theory, I used them to control how a character moved through a real map with rules, obstacles, and goals. I also gained more experience reading and following detailed programming specifications. The movement rules depended on cell types, neighbour positions, jump distance, and priority values, so the implementation had to be precise to work correctly.
This was one of the more memorable CS1027 assignments because it was more visual and game-like than a typical data structures project. Seeing the frog move across the pond made the algorithm feel much more satisfying to test.