2
\$\begingroup\$

Is there a general purpose algorithm to determine a route between rooms of a building?

Imagine a fixed-layout, single-level house with 50+ rooms. Assume I have a data structure that defines the exits of each room and the room to which each exit leads. I'd like to know how to get from room 4 in the NW corner to room 37 in the E side, say. I want the shortest list of rooms that need to be traversed. (I don't need to see this graphically in real-time.)

Is it worth finding such an algorithm or should I just 'map out' the level and use the pathfinding abilities of my game dev platform of choice..

edit: removed the A* reference

\$\endgroup\$
  • \$\begingroup\$ Your question became offtopic this way. We don't support questions asking fro technology recommendations \$\endgroup\$ – Bálint Oct 30 '17 at 11:25
  • \$\begingroup\$ I'm not really asking for a recommendation on which tech to use, just mentioning what I'm using in case it limits the solution, but point taken. \$\endgroup\$ – codah Oct 30 '17 at 11:26
  • \$\begingroup\$ May I ask why you removed the game-maker tag? \$\endgroup\$ – Vaillancourt Oct 30 '17 at 11:32
  • \$\begingroup\$ @Bálint A* is an algorithm, not a technology. \$\endgroup\$ – AlbertEngelB Oct 30 '17 at 20:43
  • 1
    \$\begingroup\$ @Dropped.on.Caprica I used the word "technology" because I didn't want to write the whole Questions about "how to get started," "what to learn next," or "which technology to use" are discussion-oriented questions which involve answers that are either based on opinion, or which are all equally valid. Those kinds of questions are outside the scope of this site. Visit our help center for more information. thing. The question asks for something, that can be answered in many different way correctly \$\endgroup\$ – Bálint Oct 30 '17 at 20:50
12
\$\begingroup\$

You have a common misconception. A* isn't made for grids, it usually uses graphs. A grid is just a specialized graph with each node having 4 edges (apart from the edges and corners).

\$\endgroup\$
  • \$\begingroup\$ Thanks, you're right I didn't think before writing that. My question still stands though-is it worth finding a 'simpler' algorithm due to my simple needs and fixed map, or go with standard pathfinding techniques? I'm new to GameMaker but can't see support for graphs. \$\endgroup\$ – codah Oct 30 '17 at 11:17
  • 2
    \$\begingroup\$ @codah A* is very simple, the only way you can go simpler is probably Dijkstra, but that isn't optimized for game development. \$\endgroup\$ – Bálint Oct 30 '17 at 11:19
  • \$\begingroup\$ Ok thanks, I'm getting the vibe that this is just a general pathfinding problem, suitable for A* etc, but maybe not easily implementable in GML(?) \$\endgroup\$ – codah Oct 30 '17 at 11:25
  • 2
    \$\begingroup\$ Although dijkstra isnt optimized it might be faster to implement without noticing any difference when its only a 50-ish node graph. You could always optimize later. \$\endgroup\$ – Niels Oct 30 '17 at 15:30
  • 1
    \$\begingroup\$ A* is very easy to implement on general graphs. It's like 50 lines of code. Should be very simple in your case. \$\endgroup\$ – mklingen Oct 30 '17 at 15:40
0
\$\begingroup\$

I cannot think of any particular general purpose solution for this, although most certainly there are people who have solved this multiple times, in various ways.

One could well use the available/built-in pathfinding abilities, this should work fine but is probably not the primary issue.

The challenge is to define an optimal node graph. This depends on how greedily the task should be solved, and also on the particular features of the environment. Apparently, a building has for example corridors, and apparently it is sometimes fastest to pass a corridor diagonally, ie. enter it by it's left wall and leaving it by it's right wall? Maybe there are rooms that need to be crossed diagonally or along some of it's walls? Staircases?

I would probably (as i like to control things myself) solve this by first creating a node graph that holds all possible nodes (points), ie. every corner and every door (even left and right edge of it separately?) is a node, or holds a node very nearby. Then I'd perform a "all nodes against all nodes" test and create a link between two nodes whenever they can see each other directly (could even use the 3D engines hit testing for that, if there is a building model available); at the same time calculate the distances as graph weights. This would create the "full set" node graph. Finally, I'd execute "go from each room to each other room" pathfinding tasks and mark any node/link that was ever used with 1. To naturally then remove from the graph all such nodes/links that were never used. This would create the minimum node graph that covers for all possible movement, suitable for runtime use, to be embedded with the application. And also be a test for the overall functionality - perhaps an extra node bust be inserted somewhere because of some unexpected reason?

\$\endgroup\$
  • \$\begingroup\$ I think I'll to accept this as the answer. I was simply trying to avoid having to 'map out' all the walls in my level as physics objects, then learn the ins and outs of whatever platform's pathfinding and all its quirks (I've done that once in Construct2 and didn't want to repeat the pain in GMS). My map is very simple and will never change. No stairs/levels; corridors are treated as rooms. Writing a 'proper' PF algorithm for this seemed overkill. I'd even be happy with a 'hacky' solution that just works. As a couple of other commenters have said, maybe just implement the A* :) \$\endgroup\$ – codah Oct 30 '17 at 21:00
  • \$\begingroup\$ I did somethng similar, a bit larger, in one project. Entered ca 7000 nodes by clicking the mouse (had some automation and visual guidance, wrote a small app). Was quite fun, actually, as my choices reflected people's real life behaviour - i had to say how people would act in various situations:-). Anyway, i then just pass that data to a standard pathfinding algo, and voilá. A* etc solvers should be standard copypaste meat, defining the good nodes&links may require a bit more effort but one can always even type coords and links in Notepad and have the proggy parse. \$\endgroup\$ – Stormwind Oct 30 '17 at 23:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.