Hey, I’ve got this room generator and it’s great so far
Issue is, this game is a first person game, so when turned into a 3D mesh it all gets a bit confusing as to where the player is going. I’d like to make a “Main” path throughout the levels, by merging rooms together to make one big room that the player can recognise as the main path to the end, while keeping the rooms around the path. Here’s my drawing of how it would work:
How can I do this? Each room is a list of BoundsInt, if that’s any help
After whatever way you are using to choose that line, look where each point on the line is, and whatever room it is in constitutes the list of rooms you need to merge, or perhaps walls to knock down.
I can’t really describe how i’d like the path to go. Definitely not shortest path, as I’d like there to be a corner in it (that is if it can, can’t really corner a straight path).
I’d like it to try and cut the rooms in half as much as possible, so there is an even amount of rooms on each side of the path. So right through the center mainly.
You could pick a room that is somewhere in the middle. This way if your start and end are on adjacent sides this almost guarantees a “bend” in the path since you walk to the middle then to the end.
Now… create an A* graph, or even Dijkstra. There are many implementations of them out there… you can google for one… note ignore the one’s that only allow 2d array grids. A generalized A* algorithm shouldn’t care. It just needs to know what nodes exist and what nodes are neighbors to each node. For example here is mine:
A*:
Dijkstra:
(some googling may help you find simpler versions of these… mine are very generalized for reuse)
Dijkstra is definitely simpler, but is slower as a result. But who cares honestly… for something this small it doesn’t really matter.
Give said algorithm your goals. You want a path from start to mid, and mid to end.
This algorithm will find the shorts path to each goal (mid and end).
You could make it respect doors, or not respect doors, by just telling it what neighbours are what. (you could define a neighbour as being 2 rooms connected by a door, or 2 rooms that share the same wall, or whatever you want really… the choices you make just alter the resulting paths)
Then… remove the walls between the rooms that the algorithm spits back.
In the end when it comes to the algorithm of your choice you could literally just brute force it by just going through your list of rooms and finding every path that goes from Start->Mid and then pick the one with the smallest number of rooms. Or more. Or whatever gives the visual results you like. In the end whatever your algorithm it’s a matter of balancing performance with the visual results you want. If it’s something you precalculate who cares if it takes a long time. If it’s done at runtime… well it should go relatively fast, but still you could put up a loading screen while you run whatever algorithm you decide to write.
Ooh, I like that idea. Although finding a room that’s somewhat in the middle may be an issue, maybe just picking the largest room that covers the middle would work well.
As for the algorithm, isn’t A* only used for cells? Also, what is Dijkstra?
Not sure what you mean by A* only used for “cells”. What do you mean by “cell”?
A* can act on any graph. Where a graph is just a bunch of vertices and their edges (vertices = node, edge = connection between nodes). From graph theory:
Your graph can be a grid, a hex grid, an arbitrary placement of nodes, a series of rooms, a multidimensional hypothetical graph of concepts, a conversation graph.
Like seriously… you could represent a conversation as a graph. Where each statement has N following statements (where N is 1 or larger). And you can create a “goal topic” and then use A* to determine what series of statements need to be stated to get to that topic in a logical manner. All you need to do is define those relationships.
Like a choose your own adventure book! (I hope that didn’t show my age…)
…
As for Dijkstra. It’s just another algorithm like A*. Actually A* is just Dijkstra with an extra step (it’s built on top of Dijkstra). Basically Dijsktra just neighbor nodes at random, A* tries the neighbor node that is closest to the goal based on some heuristic. If you always returned 0 for your heuristic in A* you’d have Dijkstra.
Think of it like this way. Say you were in a maze of rooms and you know the exit is somewhere in the southerly direction. Dijkstra would try any random room in front of them that wasn’t previously visited… where as A* would try the room to the south before any others, only skipping the south room if it’s a room we’ve already visited.
Alrighty,
I actually followed an A* tutorial for the previous iteration of this room generator (which was nothing like this, it was a 3x3 grid and it used A* to get the path from one point to another) So I believe I’ve already got a basis:
void FindPath(Vector2Int start, Vector2Int end)
{
FloorSectionNode startNode = grid[start.x, start.y];//Gets the node closest to the starting position
FloorSectionNode endNode = grid[end.x, end.y];//Gets the node closest to the target position
List<FloorSectionNode> OpenList = new List<FloorSectionNode>();//List of nodes for the open list
HashSet<FloorSectionNode> ClosedList = new HashSet<FloorSectionNode>();//Hashset of nodes for the closed list
OpenList.Add(startNode);//Add the starting node to the open list to begin the program
while (OpenList.Count > 0)//Whilst there is something in the open list
{
FloorSectionNode CurrentNode = OpenList[0];//Create a node and set it to the first item in the open list
for (int i = 1; i < OpenList.Count; i++)//Loop through the open list starting from the second object
{
if (OpenList[i].FCost < CurrentNode.FCost || OpenList[i].FCost == CurrentNode.FCost && OpenList[i].hCost < CurrentNode.hCost)//If the f cost of that object is less than or equal to the f cost of the current node
{
CurrentNode = OpenList[i];//Set the current node to that object
}
}
OpenList.Remove(CurrentNode);//Remove that from the open list
ClosedList.Add(CurrentNode);//And add it to the closed list
if (CurrentNode == endNode)//If the current node is the same as the target node
{
GetFinalPath(startNode, endNode);//Calculate the final path
}
foreach (FloorSectionNode NeighborNode in GetNeighboringFloorSectionNodes(CurrentNode))//Loop through each neighbor of the current node
{
if (ClosedList.Contains(NeighborNode))//If the neighbor is a wall or has already been checked
{
continue;//Skip it
}
int MoveCost = CurrentNode.gCost + GetManhattenDistance(CurrentNode, NeighborNode);//Get the F cost of that neighbor
if (MoveCost < NeighborNode.gCost || !OpenList.Contains(NeighborNode))//If the f cost is greater than the g cost or it is not in the open list
{
NeighborNode.gCost = MoveCost;//Set the g cost to the f cost
NeighborNode.hCost = GetManhattenDistance(NeighborNode, endNode);//Set the h cost
NeighborNode.parent = CurrentNode;//Set the parent of the node for retracing steps
if (!OpenList.Contains(NeighborNode))//If the neighbor is not in the openlist
{
OpenList.Add(NeighborNode);//Add it to the list
//Connect the two rooms together
}
}
}
}
}
Now, the issue is I’ve no actual idea what’s going on. I know about the concept of a cost in A*, but there’s like 3 of them and I’m not exactly sure why. And I’m not too sure If just nicking this code and putting it into the new algorithm is going to work exactly.