Using A* to sort non-geometric list of nodes

I run a simulation of the game world that only exists in code, and thus can’t be manually fit with a graph like most pathfinding cases. I have a Dictionary<Room, GraphNode>, where each node keeps track of the room it represents, and the rooms you reach from its room:

`	class GraphNode{
		public Room room;
		public GraphNode pathParent;
		public List<GraphNode> neighbors;

I’m trying to write a function that can take this dictionary and return a list of Rooms constituting the least number of rooms an AI must traverse to travel from their starting room to their destination:

public Dictionary<Room, GraphNode> nodes;  //This contains every node in the game		
		public List<Room> GetPath(Room from, Room to){
			GraphNode start = nodes[from];
			List<Room> pathList = new List<Room> ();
			//Do some kind of efficient pathfinding here to fill out pathList
			return pathList; //return list of rooms that the npc will pass through to travel from-to			

I know A*'s API is much more efficient and battle-tested than anything I’d write on my own, so I’m wondering if it has something I could feed my nodes dictionary and my start/destination nodes to in order to return a sequence of nodes constituting an efficient route?


It’s definitely possible to do that. But configuring everything to actually do it is probably more code than just writing it yourself. You just want a simple breadth first search, which is like 20 lines of code (though I have seen that algorithm compressed to 5 lines of code).

You can take a look at the PathUtilities.BFS method which implements the algorithm that you want.


This is incredibly useful, thank you! I appreciate the quick response :slight_smile: