Hello everyone,

So I'm making a randomly generate dungeon game, and I'm using A* to find the shortest path between rooms so every room is connected by a corridor.

So lets say I have 500 rooms. All 500 rooms need to be connected to each other. That means I need to find the shortest path between all rooms and connect them by a corridor. So what I do is I run A* algorithm 500 times to find a path for each room. lets say the time it takes for A* to find a path is 100ms. so that's 500 * 100ms = 50,000 ms or 50 seconds. Now in my engine I have A* multi-threaded. So I can run multiple threads to find the paths at the sometime. Lets say I make 6 threads. So now the math will be something like this. (500 rooms * 100ms ) / 6 threads = 8,333ms or ~8 seconds. That is a long time. I'm aiming for max of 5 seconds. On my machine I can get it to find all paths in ~2 seconds or even less. But i'm running a 6 core 3930k clocked at 5GHz, On a low end machine like a 2 core cpu that will take forever.

So what I'm wondering, is there an algorithm where I only run it once and it scans the entire grid and find a path for each room?

Thanks !

Are you saying you are generating a corridor for each room? IE Room 1 has a 499 openings, leading to 499 corridors?, or Room1 has an opening to it's adjacent rooms?

Are you saying you are generating a corridor for each room? IE Room 1 has a 499 openings, leading to 499 corridors?, or Room1 has an opening to it's adjacent rooms?

For the sake of argument lets say room 1 connects to 2, 2 connects to 3, 3 connects to 4 and so on.

But it's more like a tree of rooms. a tree would have multiple branches (the rooms) and each branch has more branches (more rooms).

Try a web search for "precomputed pathfinding." You should turn up a number of relevant techniques based on various flavors of path search, from precomputed A* to JPS and beyond.

Maybe you are looking for this: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Floyd-Warshall only returns the summed cost of every path, not the actual paths.

Try a web search for "precomputed pathfinding." You should turn up a number of relevant techniques based on various flavors of path search, from precomputed A* to JPS and beyond.

I'm sorry. I should have been more clear on what I'm trying to do. So what I'm trying to do is create a corridor between two rooms. So imagine I have nothing on the screen. I randomly generate two rooms anywhere on the map. The problem is if the player was in room one he can't go to room two because these two rooms are not connected. So I need to construct some kind of corridor to connect both rooms. I do that by finding the shortest path (using A*) between these two rooms. Once I do that I generate my corridor. All this, is happening in the loading screen. But instead of making this for only two rooms I need to do it for 500 rooms. So my ultimate goal is to try and reduce the loading time. that is all.

So in a sense i'm already precomputing the path between the rooms in the loading screen. I'm just trying to make that work faster on low end CPUs.

There are few algorithems that can create a corridor between two rooms really fast but I don't like any of them because most of them generate an L shaped corridor like this.

With A* I get interesting shapes and lengths for each corridor.

Dijkstra explores in every direction, and will give you optimal connection to all nodes it visits, from one point (or to one point, if you like, by walking 'backward').

Dijkstra can be emulated with A* where the estimate always returns 0 (useful if you also need A* in your program).

Basically with either algorithm, setup a search, and continue expanding until the search visited all roomes (or until you run out of nodes to expand).

Dijkstra explores in every direction, and will give you optimal connection to all nodes it visits, from one point (or to one point, if you like, by walking 'backward').

Dijkstra can be emulated with A* where the estimate always returns 0 (useful if you also need A* in your program).

Basically with either algorithm, setup a search, and continue expanding until the search visited all roomes (or until you run out of nodes to expand).

hmm... Interesting. Can please explain more on how that would work exactly?

Thanks :)

Not sure what part you want explained exactly, as it is just A* without estimate, and with a loop to check if all rooms have been done, but here goes:

rooms_to_visit = [......];
room_num = 0;

init_A*(initial_point);
while (true) {
    while(room[room_num] in closed_list) {
        room_num = room_num + 1;
    }
    if (room_num >= size(rooms_to_visit) break; // Found distance to all rooms in the closed list.

    // Not done, yet, expand an A* node.
    node = get_next_A*_node();
    if node == null: break;  // No point available for further expansion
    for new_point in expand_node(node) {  // Just like A*, but the estimate is always 0 instead of remaining distance to target
       store_point(new_point);
    }
}

Obviously, if you don't need A* anymore now, you can strip out the entire estimate code, as it's always 0.

And this is it. You basically have the same node expansion loop as in normal A*, but before that, you have a check what room has been visited, and you abort when all rooms have been visited, as continuing further will not give you improvements.

You can have other forms of "I visit a room" detection, like a bit "detected" in each room, and a counter that decrements to 0, and others. What is useful depends on how you store the rooms, and how you find the room from a reached point in the search.