Hey so, I’m making this level generator and I’ve used BSP to create a bunch of rooms, like what you can see here.
Each room is stored as a Vector2 for the min point, Vector2Int for the max point, and a Vector2Int for the center. The floor is just a list of rooms.
I also have a list of a class called RoomConnection, which basically marks which room is connected to which.
public class RoomConnection
{
public Room one;
public Room two;
public Vector3 doorPos; //Where the door would be
public RoomConnection(Room one, Room two)
{
this.one = one;
this.two = two;
}
public List<Room> GetRooms()
{
List<Room> list = new List<Room>() { one, two };
return list;
}
}
I’ve got to make a path from one point to the center, then from the center to another point. How can I do this? Somebody suggested using A*, but I don’t really know how to do it in this use case.
In the A* algorithm and most of the pathfinding algorithms you need to define some sort of graph.
You can define each room as a node and each door/connection between them as vertices. So for creating this graph you technically don’t need the position of the rooms only the list of connections is needed. Then you can use the A* algorithm on it with the euclidean distance as the heuristic.
Then you can either define your character’s movement by making him move from the center of a room to the center of the next room or door to door (the latter one would make the movement more natural in my opinion).
I think this is what you are exactly looking for. It explains in detail how to create your own pathfinder using C#. The source code is available on GitHub.
So in that post I showed my modular/generalized version of A*. Here it is stripped out of the spacepuppy framework and without the “stepping” feature which just confuses some people unfamiliar with A*. (basically my algorithm could be ran all at once, or spread across multiple frames in a coroutine using the “stepping” technique to reduce overhead)
public interface IPathResolver<T>
{
T Start { get; set; }
T Goal { get; set; }
IList<T> Reduce();
int Reduce(IList<T> path);
}
public interface IGraph<T> : IEnumerable<T>
{
int Count { get; }
IEnumerable<T> GetNeighbours(T node);
int GetNeighbours(T node, ICollection<T> buffer);
bool Contains(T node);
}
public interface IHeuristic<T>
{
float Weight(T n);
float Distance(T x, T y);
}
public class AStarPathResolver<T> : IPathResolver<T> where T : class
{
#region Fields
private IGraph<T> _graph;
private IHeuristic<T> _heuristic;
private BinaryHeap<VertexInfo> _open;
private HashSet<T> _closed = new HashSet<T>();
private HashSet<VertexInfo> _tracked = new HashSet<VertexInfo>();
private List<T> _neighbours = new List<T>();
private T _start;
private T _goal;
private bool _calculating;
#endregion
#region CONSTRUCTOR
public AStarPathResolver(IGraph<T> graph, IHeuristic<T> heuristic)
{
_graph = graph;
_heuristic = heuristic;
_open = new BinaryHeap<VertexInfo>(graph.Count, VertexComparer.Default);
}
#endregion
#region Properties
public bool IsWorking
{
get { return _calculating; }
}
#endregion
#region IPathResolver Interface
public T Start
{
get { return _goal; }
set
{
if (_calculating) throw new InvalidOperationException("Cannot update start node when calculating.");
_goal = value;
}
}
public T Goal
{
get { return _start; }
set
{
if (_calculating) throw new InvalidOperationException("Cannot update goal node when calculating.");
_start = value;
}
}
public IList<T> Reduce()
{
if (_calculating) throw new InvalidOperationException("PathResolver is already running.");
if (_graph == null || _heuristic == null || _start == null || _goal == null) throw new InvalidOperationException("PathResolver is not initialized.");
var lst = new List<T>();
this.Reduce(lst);
return lst;
}
public int Reduce(IList<T> path)
{
if (_calculating) throw new InvalidOperationException("PathResolver is already running.");
if (_graph == null || _heuristic == null || _start == null || _goal == null) throw new InvalidOperationException("PathResolver is not initialized.");
this.Reset();
_calculating = true;
try
{
_open.Add(this.CreateInfo(_start, _heuristic.Weight(_start), _goal));
while (_open.Count > 0)
{
var u = _open.Pop();
if (u.Node == _goal)
{
int cnt = 0;
while (u.Next != null)
{
path.Add(u.Node);
u = u.Next;
cnt++;
}
path.Add(u.Node);
return cnt + 1;
}
_closed.Add(u.Node);
_graph.GetNeighbours(u.Node, _neighbours);
var e = _neighbours.GetEnumerator();
while (e.MoveNext())
{
var n = e.Current;
if (_closed.Contains(n)) continue;
float g = u.g + _heuristic.Distance(u.Node, n) + _heuristic.Weight(n);
int i = GetInfo(_open, n);
if (i < 0)
{
var v = this.CreateInfo(n, g, _goal);
v.Next = u;
_open.Add(v);
}
else if (g < _open[i].g)
{
var v = _open[i];
v.Next = u;
v.g = g;
v.f = g + v.h;
_open.Update(i);
}
}
_neighbours.Clear();
}
}
finally
{
this.Reset();
}
return 0;
}
private VertexInfo CreateInfo(T node, float g, T goal)
{
var v = new VertexInfo();
v.Node = node;
v.Next = null;
v.g = g;
v.h = _heuristic.Distance(node, goal);
v.f = g + v.h;
_tracked.Add(v);
return v;
}
private static int GetInfo(BinaryHeap<VertexInfo> heap, T node)
{
for (int i = 0; i < heap.Count; i++)
{
if (heap[i].Node == node) return i;
}
return -1;
}
/// <summary>
/// Reset the resolver so a new Step sequence could be started.
/// </summary>
private void Reset()
{
_open.Clear();
_closed.Clear();
_tracked.Clear();
_calculating = false;
}
#endregion
#region Special Types
private class VertexInfo
{
public T Node;
public VertexInfo Next;
public float g;
public float h;
public float f;
}
private class VertexComparer : IComparer<VertexInfo>
{
public readonly static VertexComparer Default = new VertexComparer();
public int Compare(VertexInfo x, VertexInfo y)
{
return y.f.CompareTo(x.f);
}
}
#endregion
}
(original version with the stepping algorithm and object pooler for optimization)
It does rely on using a BinaryHeap, which can be found here:
(this class has no dependencies and can be copied pasted easily)
To use it you just need to create implementations for IHeuristic (that’s what calculates distances). And the graph to operate on (that’s what contains the list of rooms and the connections). This is what facilitates the algorithm knowing what sort of nodes its acting on… in your case “Room” and “RoomConnection”:
public class RoomHeuristic : IHeuristic<Room>
{
public float Weight(Room room) { return 0f; } //don't really need a weight, weights can be used to incentivize/deincentivize traveling through a node. Think of it like how a road is more desirable than a swamp. You could weight the road more positively than the swamp to make it more desirable
public float Distance(Room x, Room y) { return Vector2Int.Distance(x.Center, y.Center); }
}
public class RoomGraph : IGraph<Room>
{
private List<Room> _rooms;
private List<RoomConnection> _connections;
public RoomGraph(List<Room> rooms, List<RoomConnection> connections)
{
_rooms = rooms;
_connections = connections;
}
public int Count { get { return _rooms.Count; } }
public IEnumerable<Room> GetNeighbours(Room room)
{
foreach(var conn in _connections)
{
if(conn.one == room) yield return conn.two;
else if(conn.two == room) yield return conn.one;
}
}
public int GetNeighbours(Room room, ICollection<Room> buffer)
{
int cnt = 0;
foreach(var conn in _connections)
{
if(conn.one == room)
{
buffer.Add(conn.two);
cnt++;
}
else if(conn.two == room)
{
buffer.Add(conn.one);
cnt++;
}
return cnt;
}
}
bool Contains(Room room) { return _rooms.Contains(room); }
}
(note - my implementation of the graph is very naive here for demonstration purposes. There is a way to group those connections that would be faster to read from rather than looping the entire list. Such as using a dictionary or the sort. But I went with a way that fits what you already have shown up to this point and is easy to understand)
…
Now just operate it:
var heur = new RoomHeuristic();
var graph = new RoomGraph(allMyRoomsList, allMyRoomConnectionsList);
var resolver = new AStarPathResolver<Room>(graph, heur);
resolver.Start = roomToStartIn; //how you determine your start room? if you only know the door just loop over the rooms and find the room with the door
resolver.End = roomToEndIn; //again, you need to determine this
var path = resolver.Reduce(); //this will be a list of all rooms that should be conjoined together
Hello. I have written a series of tutorials on Pathfinding in Unity using C#. It is a four-part series of tutorials where I go in-depth to solving the pathfinding problem using C# in Unity.
In Part 1 we create a generic pathfinder that is algorithm agnostic. Then we create three implementations of the pathfinder using the A*, Djikstra and Greedy best-first algorithm.
In Part 2 we apply this generic pathfinder to solve the 8 Puzzle Problem (to show how pathfinding can be used to other types of problems).
In Part 3 we apply the same generic pathfinder to solve pathfinding for a 2D grid-based map.
Finally, in Part 4 we apply the same generic pathfinder to solve pathfinding for a graph-based map.
You can try out the solution in the WebGL Pathfinding Playground where you can change the algorithm type (A*, Dijkstra and Greedy best-first) and the cost function.
I hope you can apply the same generic pathfinder to your problem by either doing a small extension for your data type or reusing the datatype that I provide a rectangular grid-based map. If you have any further issues please do not hesitate to contact me.
