Sign in to follow this  

Find all paths in a single iteration?

This topic is 732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 !

Edited by FantasyVII

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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).

Edited by FantasyVII

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

procedural-content-corridor-diagram-1.pn

 

 

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

Edited by FantasyVII

Share this post


Link to post
Share on other sites

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).

Edited by Alberth

Share this post


Link to post
Share on other sites

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 :)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

I am programming similar stuff to you while you are also working on it.

 

What I did was draw rooms in a map first. Then snake around tunnel elements. All these elements would be disconnected. Nu double tunnels or rooms overlapping.

 

Then I would pathfind each tunnel element, trying to reach the primary upstairs, until it had a dead end. It knows where the upstairs is. Each pathing attempt in a section, the dead-end usually closest to the upstairs, I would mark.

Next I went back and at marked each-dead end I tunneled to another tunnel element or room, connecting the two.

 

Then I would pathfind everything again with an A* and again newly mark all unconnected dead ends. If everything was connected with everything else, it would tell me and I was done.

 

In the end that worked pretty well. It didn't overconnect everything (a problem I had at first) and it also didn't create a linear pattern of room-tunnel-room-tunnel.

 

Not the most elegant, but it worked for me. Once I had it working properly, it worked pretty cool. Still, it does leave a bit of unused space (walls that never become rooms or tunnels) on the map. That, I can patchwork up.

 

 

How many iterations it takes depends on the size of the map. But for 41x41, I think it needs 3 or 4 on average.

 

 

I don't think speed is really a problem unless you have an algorithm that fails 90% of the time and has to start over and over again because it can't meet certain conditions you set.

 

 

 

If you want it to branch out like a tree, you can program it like that. Place a room somewhere in the middle, tunnel a certain direction for a certain distance, create another room B1. Then go back to room A, tunnel in another direction, create room B2. Go to room B1, create two more tunnels that end in rooms C1 and C2, go to B2, create C3 and C4, etc.

Edited by Almeisan

Share this post


Link to post
Share on other sites
Sign in to follow this