koobas.hobune.stream
Room Path Generator
So I have been trying to write a script in JavaScript, but have been pretty stumped on this for the past few hours. So pretty much, here is the scene: There are multiple rooms with varying amounts of doors that lead to other rooms. What I want, is for an AI to be able to find a path from what ever room it's in, to another room. To be able to find every door in which it needs to get through to reach it's destination room.
Here is an example along with a picture:
Let's say the AI is in room number 2, and wants to go to room 7. I need an idea for a script that calculates what doors it will need to go through to make it from room 2, to room 7. For example, it would have to take the door that leads to room 1, the door that leads to room 3, then the door that leads to room 7. (Each black line represents which door leads to which. Example: The door on the right of room 1 leads to the middle door in room 3)
I have had multiple ideas, all failing. I am asking simply for an idea, a place to start with this. I've tried for several hours, almost making it nowhere. Thanks in advance.
Sounds like you're looking for Pathfinding.
See http://answers.unity3d.com/questions/9025/pathfinding-tools-in-unity.html
Not quite what I was looking for. That seems like more for a 3D environment, going around obstacles, while I'm trying to create a script that goes from one room to another. Thanks for the help though!
It's still a Pathfinding problem, even if those specific libraries wouldn't be pertinent to this case.
Specifically, your case is finding the single-pair shortest path on an undirected graph with unit weight.
Edit: looks like you can use fancy algorithms (Dijkstra, Thorup), but a simple breadth-first search will do the trick here.
"simple breadth-first search" Is what I was originally doing. What got me was how to store the data. Have an idea for that? (A$$anonymous$$A how to save the paths it has taken, then only use the correct one)
So this SO question might be of use (though it isn't quite right) as might this blog post.
The basic concept is that as you enumerate, you store the previous node in an array. I hope the below explanation is followable.
So: say I have the graph where node 0 is connected to node 1, 2, and 3 and Node 3 is connected to nodes 4 and 5. I want the path between nodes 0 and 5.
I create an
int[] previousarray with the number of nodes in my graph (6).I also create a
bool[] visitedof visited nodes and set all 6 to false.I mark my starting node, 0 as visited with
visited[0] = true;.I enumerate the connections to 0 (1,2,3), and mark each as visited in the same way.
I store the previous node I'm co$$anonymous$$g from:
previous[1] = 0; previous[2] = 0; previous[3] = 0;.Then I enumerate 1 (0 is visited so do nothing)
Then I enumerate 2 (0 is visited so do nothing)
Then I enumerate 3 (4,5) and mark each as visited.
I store previous nodes:
previous[4] = 3; previous[5] = 3;Ah-ha! I found 5, which was my goal. In order to get my path back, I simply use each array value as the indexer for the next.
End => 5
previous[5] => 3
previous[3] => 0
$$anonymous$$y path is that sequence reversed: 0 - 3 - 5.
It's what I saved in the array as I enumerated. Since previous[5] == 3 my next call should be to previous[3]. It does feel pretty weird to use values to index like that. You could also use a Dictionary (you said JavaScript, right? So -- think associative arrays) to store a string -> string mapping.
An example with strings might make more sense than numbers. Imagine we're solving the shortest path problem for this food chain:
I want to find the shortest path from green plant to "owl". As I enumerate the paths out of "green plant", I'm saving "green plant" as the previous value of "beetle", "grasshoppper", "wood mouse", and "snail". Like so: previous["wood mouse"] = "green plant".
Here's what the full previous[] array should look like when you're done (I enumerated from left to right):
// Enumerating green plant...
previous["beetle"] = "green plant"
previous["grasshopper"] = "green plant"
previous["wood mouse"] = "green plant"
previous["snail"] = "green plant"
// Enumerating beetle...
previous["shrew"] = "beetle"
previous["spider"] = "beetle"
// Enumerating grasshopper... (nothing, because they're all visited already)
// Enumerating wood mouse...
previous["owl"] = "wood mouse"
Starting at our end point ("owl"),
previous["owl"] = "wood mouse"
Now we use "wood mouse" as our index to find what its previous link was.
previous["wood mouse"] = "green plant"
So our path is owl => wood mouse => green plant.
P.S. Notice how really, you're making a data structure that can be used to find the shortest path from your starting node to any end node. All you have to do is at the end of making your full enumerated paths, start at a different index in your previous array. Pretty neat!
P.P.S. I realized that what I described in my previous comment wasn't quite right. When you first encounter each node, you should mark it as visited, rather than when you begin to enumerate that node's neighbors. If you don't, and you have loops or cycles in your graph, you might run into trouble. I fixed it in the comment above.
