pathfinding_johnson_reupload

Abstract:  a demonstration of the A* pathfinding algorithms as according to the rubric of a Game AI class

Controls: scroll up/down - zoom in/out

direction keys (wasd or arrow keys) - pan around the map

ui buttons navigate between different maps, switch between modes, and otherwise do what they say on the button

Heuristic button switches between pythagorean distance, manhattan distance, minimum of x and y distance, and squared pythagoreon distance.

Step interval slider goes from .005 seconds minimum to 1.3 second maximum.

6 other buttons switch between 6 map/modes

Explanation

How did I deal with scaling up and partially blocked tiles in grid based pathfinding?

I scaled up by a factor of 2 such that each pathfinding grid square was 4 world tiles.  This is a 75% reduction in area.  I could have gone by a 3x reduction for 88% less area, but that reduction isn't that much less computation time and it tends to make narrow passageways untraversible.
Sometimes partially blocked tiles will be traversible.  Each type of tile has a value assigned to how 'traversible' it is.  these values are summed up and then if the average traversibility is high enough, the pathfinding grid will be enabled over those 4 tiles.  This allows pathfinding over squares that are just blocked in the corner and over the lake tile type.

How did I design my waypoints?

I didn't use a particular method but was inspired by the samples shown in class and tried to place enough to give every area a way to get through.  I don't fill a room with waypoints, but I generally placed them at every entranceway, at corners, when there's been too long between previous waypoints, or to access nooks of a room.  I pruned my maps later to remove the super redundant ones.

What are the advantages and limitations of my approaches?

Both my grid and waypoint-based navigation methods are very dynamic.  With more time to work I could scale them up and make them more procedural.  The biggest advantage was importing the priorityQueue class normally availible in dotnet cs.  This allows me to perform normal a* operations at a blazing fast pace.

What would I do differently if I had different maps or a larger/smaller agent.
I had to design for three different maps in the first place, so my approach adressed all kinds of map.  If the agent represented a much larger area of map though, such as being 5x5, I would have to do things a lot differently.  I think a grid-based approach for such a thing is ill-advised, but if I had to I would make a function to remember walls between any two grid spaces instead of just if a grid space is traversible.

Code explanation:

my code got very messy as I changed tacks over the course of the project. Heres the somewhat chronological rundown.

TILE BASED:

MapMakerScript.cs - takes input from text files and converts into tilemaps. As it does, it executes a couple functions on the map visualizer
to make it work.

MapComputer.cs - visualizer of the maps. Manages two tilemaps, one consisting of the literal terrain from the map files, and the other
consisting of the scaled up navigating tilemap.

Contains A* implementation, held semi-self-enclosed.

This was reprogrammed completely, so its a mess of functionality.

GENERAL:

PriorityQueue.cs - implementation of priorityqueue ported from https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src

/System/Collections/Generic/PriorityQueue.cs

MIT license

(its should be in system.collections.generic but unity refuses to update anything)

CamController.cs - a basic camera controller to let the camera pan and give the user more agency. Allows for zoom and pan

WAYPOINT BASED:

the terrain tilemaps for all three are just taken from the scenes of the previous three tile-based interpretations. Waypoints are placed
randomly and then cleaned up

singlepoint.cs - runs each waypoint. Serves multi duty to remember its neighbors, know its heuristic and distance when asked, remember its
parent when it joins the open list, and other stuff to make it useful.

WaypointControl.cs - the center control of the waypoint based pathfinding. Knows every singlepoint, draws lines between them at the start,
and then executes A* when start and end have been chosen.

OTHER:

miscellanious features were implemented with unity objects, such as the UI. Other things were crammed into other tricks I needed to do to get
them to work. None of these are significant.