enter image description here

Hey Guys,I am trying to implement dungeons into my 2d RTS ish game.The dungeons is made out of rooms, you start at the top, and you can unlock rooms with scouts.The picture is the unlocked version of the dungeons, except for the middle part where it says "locked".For example the long rooms in the picture are actually consists of 3-4 rooms. The dungeon is handbuilt by me, there are no obstacles except for unlocked areas and walls.No need for collision avoidance.The boxes with up and down indicates "ladders", when a unit wants to go up/down it just fades out and fades in the new layer, no moving up/down animation.You control the units by mouse.No jump mechanic etc, they just move flat on the green areas.

So I think I need to calculate and store which ladders(or nodes) the unit needs to take to reach the target, I need to check if ladders are connected to each other I think.But I don't know, not a great programmer.I have looked into Astar and dijkstra's algorithms but they seem complicated to implement, there is a built in Astar in gamemaker but it uses grid system and doesn't seem to fit to my problem. Do I really need to learn one of those algorithms or can I get away with a simpler approach?Any pseudo code you guide me with?I would really appreciate the help.I know a bit of c# and unity.Thanks a lot!

  • \$\begingroup\$ Do you have your rooms in memory (in a form of which rooms are neighbors or can be accessed from one) What do you want to achieve? If a room is reachable or calculate the path the unit needs to take \$\endgroup\$
    – Zibelas
    Commented Sep 4, 2020 at 11:48
  • \$\begingroup\$ No, but that is a good idea I can store the rooms in memory with its neighbours and whether they are unlocked or not.I can check if a room is reachable on my own I think, what I really need is to calculate the path unit needs to take(hopefully shortest) \$\endgroup\$ Commented Sep 4, 2020 at 11:58
  • \$\begingroup\$ Since your rooms are static, you could store as well the distance in each room from entry to all of its exits. Your map is not too big and you should be able to calculate the total distance to your destination with all possible ways and simply pick the shortest. You could do this even once for each map IF performance should be a problem and just save the result for the longer roads and calculate the shorter on the fly. \$\endgroup\$
    – Zibelas
    Commented Sep 4, 2020 at 12:09
  • 1
    \$\begingroup\$ A* and Dijkstra's algorithm are not as bad as they may look, and you may find implementing them is informative and even fun. We'd be happy to help you overcome an obstacle if you've gotten stuck somewhere in attempting to implement either algorithm; just edit your question to show us how you've tried approaching it so far, and where you need help with it. Or, if you can break your map into tiles that all have the same cost to traverse, breadth-first search will find all shortest paths with much simpler code than Dijkstra's. \$\endgroup\$
    – DMGregory
    Commented Sep 4, 2020 at 13:39
  • \$\begingroup\$ Hey thanks a lot, I managed to solve the problem with breadth first seach, it was easier than I thought to implement, maybe one day I will convert it to Dijkstra and A*star who knows! \$\endgroup\$ Commented Sep 5, 2020 at 13:23

1 Answer 1


For a single agent or multiple non-colliding agents

Try hill-climbing, how a hound might follow a scent, or the game of "you're getting warmer".

The way to do this is to pick the target node you want to do to, then diffuse a (floating point) scent value outward from the target room, through it's neighbouring nodes; then their neighbouring nodes; and so on till the whole graph is covered (you will need a suitable reduction formula as the scent spreads outwards). These scent maps are also commonly known as heat maps. The dark blue in this image looks like your where your target room would be diffusing heat / scent outward:

enter image description here

(Obviously it will look a little different in your case, but the principle is the same.)

Once there is scent spread throughout the map, you walk the entity from the current room to the neighbour with higher scent, until there are no more neighbours with a higher scent, at which point you've reached the target room.

For your locked door, we lock that tile or room to a scent value of 0 - this means it is never an attractive location to walk to. Unlocking the door means that location can once again receive scent, just like any other.

For multiple colliding agents

Collaborative Diffusion is conceptually simpler than A* if not as efficient in all cases (which for a simple game like yours, won't matter). It is hill-climbing, but supports having multiple (colliding) agents avoid one another.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .