Need help with random map/city generator

[Imaculata]

One of the things I'm still trying to work out, is how to have rooms that have blockades. See, my current dungeon generator creates rooms that have a linear path, as in: You can reach every door from any door in the room. But what if there is some sort of separation in the room, that cuts it in two? I'd like to have such dungeon features, but I do not know yet how to make this work, without the game creating unsolvable mazes. I suppose I'd need to have sub categories of rooms, so that the game cannot block off the road to the exit by accident.

[Nixola]

You could have a pathfinding algo such as A*; of it can't find a way you don't put that blockade

[Robin]

The simplest way I can think of is:

1. keep a count of all the "nodes"
2. create an empty set Visited and an empty set Frontier
3. temporarily make the blockade
4. start from one of the nodes, add that node to Visited and Frontier
5. pick a node from Frontier, if Frontier is empty go to step 8
6. for every node adjacent to the node you just picked, check if it's in Visited, and if not, add it to both Visited and Frontier.
7. go back to step 5.
8. count the number of nodes in Visited. Is it equal to the number of all nodes? Congratulations, make the blockade permanent. Is it less? Remove the blockade and maybe try again somewhere else.

It's O(N), where N is the number of nodes in the level, so if you want M blockades, the total thing will be O(MN).

[Imaculata]

Thanks for the tips, but I'm not sure if I understand the process completely. Are you saying that I should basically create a function that tries to reach the exit with the blockade in place? And then remove it, if it can't reach the exit? That sounds a bit cumbersome. I wonder if there isn't an easier way to do this. Maybe I can set up some room categories that make sure that a room that blocks off a certain direction is never placed on the main chain.

Here is how this could work. Suppose room B is connected to room A and room C, with its left and right door. And the game wants to place a random blockade in room B, which is a template that completely overwrites room B.

Code: Select all

--ROOM A --- ROOM B --- ROOM C-- 

The game could then check if the blockade is in the category of rooms that block the left-right connection, or it could choose to only pick rooms from categories that do not block off the left door from the right door.



Direct link to the screenshot

Small update, I finally added doors, and fixed the doorways. Here is how it works:

Doors
The crawler adds new doors to a list, as it visits new rooms. Each room has a reference to one of the doors in this list. This is important, because two adjacent rooms basically use the same door, but the door has to be rendered twice. So if the door is open in one room, it will automatically be open in the other as well, since they use the same door reference. This will also cause them to animate simultaneously, but I have not added that yet. I am pretty proud how well this is working.

Room batch rendering
Rooms are also rendered as batches. So first the game checks which rooms it wants to render, and if they are inside the boundaries of the level. It tries to render the room you are in as well as adjacent rooms, so things don't pop onto the screen. And this is working just excellent.

The main crawler
I fixed a small problem in the crawler, because I forgot to change the room type of the rooms that it visited. The crawler can only expand the initial chain to rooms that have the "no room"-type, and it should set them to the "empty room"-type if they have been visited. But I forgot to do this, so this allowed the crawler to retrace its steps across rooms it had already used. This made for some interesting labyrinths, but I'd rather have some more control over the process. It's fixed now.

Room connections
I fixed the problem with the doorways not being carved out correctly. The game now first creates all the rooms and their doors, before it checks every room in the level, and only then it draws a doorway for every door that a room has. So drawing doorways is now the last step in the tile process, as it should be. This only needs to be done once at the start of the level.

To do next
Next I'll clean up the way the doors render, and add their collision detection and functionality. Some doors will close behind you, and only reopen once you kill all the enemies in the room. I'll have to check the status of a room, and open the doors when the room is clear.

For this to work, I'll need the dungeon-generator to go over the whole dungeon, and randomly change the door type of any doors that are normal. (I don't want to replace the boss door, or locked doors, by accident) Some doors will be open, some will be closed, and some will lock behind you.

[Imaculata]

Link to image

Another update.

As you can see in the screenshot, door posts now render correctly. I render the bottom and top part of the door as separate elements, which allows them to now blend pretty seamless with the walls. The player is rendered in between.

I also added some code so that staircases now reduce the player's speed by half. Plenty of tiles already have unique identifiers, but now it is simply a matter of doing something with that information.

Doors also automatically animate if they are flagged open or closed, and play a sound when they do. The game checks the state of doors only if the player is in the room. So if the player has completed the objective of the level, and he reaches the exit room, only then does the game update the door, and make the exit open. This is good, because you want to see the door opening, and I don't want the game checking every door in the dungeon all the time.

[Imaculata]

Mini crawlers!

I've finally added additional crawlers. After completing the main chain, the game tries to start a mini chain at any unused room that is adjacent to an empty room.

I noticed however that this method has a bit of a side effect. With each chain I add, more empty rooms are added to the level. Which means that the more crawlers I run, the smaller the chance that the chain is attached to the main chain (because it has more empty rooms to choose from). So sometimes when you wander the maze, you'll notice that there are entire sections which are completely linear (probably because one chain was attached to another chain).

I'm currently pondering if I should just add a rule that makes sure that every crawler always starts from a room in the main chain. I suppose I could also make it random, and have the game randomly pick one of 4 level creation methods.

Other updates

Doors now automatically animate, and auto-close or open with sound effects. The camera system moves from room to room, like in the classic Zelda, and is no longer attached to the player. I also removed an exploit where the player could spam his sword absurdly fast by hammering the movement keys.

[Imaculata]

Randomized treasure chests

I implemented some new code, that will manage all the treasures in the game. As the dungeon is being built, it grabs one random weapon, all of the mandatory items (map/compass/crystalball), and a random number of keys, to create the treasury table. It will try to add a treasure in the final room of every chain it makes.

I also added a new table to the room-templates, which lists a ton of information about where the game can spawn various objects. One of those random objects, is treasure chests. After building the dungeon, the code will go over all the rooms in the game, and check if they contain treasures. If they do, the game will check if the room has one or more chest spawn locations. It will then pick a random location to place the chest, and update the tiles and collision accordingly.

Toggle blocks

The game can now keep track of whether the player is standing on top of a toggle block, and allows the player to drop down from it. I still need to add a switch that the player can strike with his sword, to toggle the blocks up and down. This is identical to the way switch blocks work in Link to the Past and Link's Awakening. I may also need to add an option for the player to drop down from higher ground.

To do

Treasure chests cannot be opened yet, which is next on my list. There's an annoying bug where all background animations (torches and stuff) that happen to be in a room on the far right edge of the level, won't animate. This is probably a dumb mistake on my part, but I can't for the life of me figuring out where the error is. I also need to sort out a bug in the dungeon crawler code. It occasionally creates a connection to a room outside the level bounds (which can crash the game), or it creates a door that is not mirrored in the room on the other side of it. I could be lazy about it, and just have the code double check all the door connections after building the dungeon. But I think I want to solve what is causing this.

[Imaculata]

I made an unexpected amount of progress on my rogue-like Zelda game. I actually have some of the items working, the chests working, and there is a mini map now.


Link to the screenshot

Mini map!
I have the mini map working!!! Whahooo! It displays a limited portion of the level, along with a tiny red dot to indicate where the player is. If you collect the map, it will also show unexplored rooms in a darker color, but without drawing the doors. If you have the compass, it will draw a yellow dot where the exit is. If you have the crystal ball, it will draw any rooms that you've visited and which contain secrets, in orange. It will also play a melody whenever you enter a room that has a secret.

In Zelda on the game boy, the compass had sort of this functionality. But it only showed where the goal was and the locations of keys on the map. I've decided to change things back to the way they were in Zelda 1. The compass only shows the goal, and a new item (the crystal ball) shows all of the secrets. My game will have a lot more variations in the way treasures can be hidden, so an item that provides hints is essential.

I'm not sure yet if the crystal ball should also reveal where hidden rooms are. I haven't implemented hidden rooms yet, but I will certainly add them, once I've also added bombs to blow up those walls. The hidden rooms could cause trouble, depending on how I implement them. If they contain essential items, and the player runs out of bombs, then the player is stuck. But maybe I can tell the game to always spawn monsters that drop bombs, in a room that contains a destructible wall.

Alternatively, the crystal ball could just highlight the room that contains a destructible wall instead, since it only affects rooms that you've visited.

Treasure chests are working!
Treasure chests are now placed randomly at the end of a chain. The game grabs a random treasure, from a list of possible treasures, and associates it with the room. Players can interact with the chest to receive the item, which looks and sounds exactly as you'd expect, if you've ever played a Zelda game. A level always contains the same fixed items (compass, map, crystalball, bosskey), one random weapon, one or more random keys, and some coin rewards.

Huge chest is working
The game always spawns a treasure room in the location of the special weapon, with a huge chest.

Holding items overhead
When you get a special item, the item is now rendered in the hands of the main character as he is holding it up. Its kind of nice to not have to check the console every time to see what item I got.

Pushing is working
The player now plays a push-animation when running up against collision.

Foreground tiles
The game now also renders tiles in the foreground, allowing the player to pass behind certain objects. I made a separate render layer for this.

The hud is working partially
I've added a hud for your health that also works, and starts beeping at 1 heart or less. The game now also display your collected keys, and dungeon-items.

Boss doors added
The game now adds a locked boss door to the boss room, and the boss key is the only item that can open it.

Vases
The object layer has been implemented. I can now populate the rooms with random assortments of objects, such as destructible vases, toggle switches and such.

Toggle switches work
After a lot of work, I finally got the toggle switches working. When struck by a weapon that can hit toggle-objects, it will scan the room for tiles that have the attribute to be toggled. It will then animate the tiles, and make them pop up, or drop down from the ground. The game also flags the player as being on higher ground, if he happens to be standing on them when they pop up.

Hit detection is working, sort of
I implemented a primitive sort of hit detection to the game. I can spawn a temporary collision volume, which then checks which tiles it is hitting. Those tiles are then checked for their collision. If they contain destructibles or switches, those scripts will then fire.

[Nixola]

First of all, that game looks really nice! Will you have any demo version soon?
Second, maybe you should open a topic in the proper section for this?
Third:

But maybe I can tell the game to always spawn monsters that drop bombs, in a room that contains a destructible wall.

That won't work, since the player will be able to use the bombs for other things and then still be stuck. Can you maybe tell the game to only put "optional" items in the secret rooms? That way they're not necessary, but still useful. Maybe add a class of rare items that has a higher chance to spawn in secret rooms?

[Imaculata]

I could do that. Another option that I've considered is having enemies respawn in rooms after a while (so you grind them for more bombs) or to place access to a shop at the start of the dungeon.

Also, I think I will open a new topic for this, (HERE) since the game has now progressed way beyond just a simple question about random dungeons. As for a demo, I'd love to have you guys check it out, but I think I need a little more game play before I do that. I've only just implemented damage (the player couldn't even get hurt before), and traps (which shoot projectiles from walls). But there's still very little game to speak of. The collision detection is rough, none of the weapons work, and there are no enemies to fight what so ever. The game doesn't even drop loot yet, only items from chests. So that's not really a game yet.

I'm still fiddling around a lot with the dungeon algorithm. I'm glad it works, but I'm not happy with the scope of the dungeons. All dungeons tend to turn into big blocks. The game basically uses up all the available space with rooms. And while this does give elaborate mazes, it also means a lot of endless backtracking, and slogging through long linear series of rooms. I think I need to tone down how long the crawlers can make the tunnels, and maybe add some random rooms that block the crawler, so it has to go around. I'd love the have the dungeon look more like an octopus, rather than a big square.

The new topic about this game is right here