Pathfinder
Project Type: Forsbergs skola / solo project
Software Used: Unity
Languages Used: C#
Primary Role(s): Game Programmer
Team Size: 1
Project Time: 2 weeks
About
Pathfinding assignment with a twist, I decided to make a pathfinding problem using Breadth First Search algorithm to find the shortest and safest way through a maze where the player needs to collect all keys while dodging traps that kill him if stepped on. After collecting all keys the door to exit opens, player has to get through the exit door to complete the level.
Player can move Upwards, Downwards and sideways 1 square at a time, the State.GetSuccessors gets the neighboring states up, down, left, right only if its walkable(not a wall, trap or enemy) and PositionExists so it wont go out of the 2D array. State holds reference to the Door (position and isOpen) and List (positions).
Algorithm & Data Structure:
Made Breadth First Search Algorithm containing Hashset for visited nodes and Queue<State[]> todoPaths.
I chose to keep the keys in a list because the keys will never be more than 5 So its easy to remove when reaching the keyPosition. Adding is O(1) Removing is O(n). I always have a fixed number at the start for the keys so I chose to use a list.
Path:
After finding a path it gets shown on the screen as cyan, make the cell.visited from the path to visualize it. Then move the player with a coroutine one step at 0.5s at a time.
The Grid:
Grid consists of a 2D array. Width 20 and Height 15 = 300 squares. Player can move Up, Down and sideways 1 square at a time Each cell has int cost, bool walkable, bool trap. The grid is a ScriptableObject which can be configured in Unity inspector, change cell.walkable to false if you want walls, cell.trap to true for traps or set the cost if you want the player to be slower or not to consider cell unless its worth the extra cost. Choose where in the Grid you want the keys and door positions. After making your desired map, drag n drop the SO into the GameScripts to reference it in the GridSlot.