sunjay / caves Goto Github PK

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

Procedurally generated levels

N = number of levels

Goal: collect the giant golden treasure on the last level (level N)

• Points for defeating enemies (enemies randomly spawn in a way that is independent of the randomness of the level generation--different every time) - more points for beating stronger enemies
• Need to collect special treasure keys on each level - one per level - in order to unlock this final room
• Fog of war - there is a map view that you can use by clicking SELECT - only shows rooms and passages you have explored so far
• 4-6 rooms on each level with 2-3 up/down staircases leading between levels
• you can freely go between levels once you've found a staircase
• levels get harder as you go up (fewer resources + more/harder enemies)
• weapons get better as you get more experience
• some rooms are locked and require a room key found in another random room
• B = block/defend yourself (shield)
• A = interact with whatever you are facing
• Y = attack whatever are facing
• movement controls:
  • tap arrow: face that direction
  • hold arrow: move one tile in that direction
• chests - treasure key, room key, potion
• one room on each level contains a "boss"/"challenge" which can be a bunch of enemies or one big one - room gets locked, you get a heart container in a chest if you beat all the enemies

Level generation parameters:

• N = number of levels
• n = current level being generated (1 to N inclusive)
• max_rooms = maximum number of rooms per level, can be a function of n
• locked_rooms = fraction of rooms that should be locked, must be between 0.0 and 0.5, between 0 and (locked_rooms * rooms.len()) will actually be locked, level generation must guarantee that there is a way through the level - may actually be implemented as a function of the number of rooms instead of a fraction so there is complete control and even a constant number can be used if needed

Level generation procedure:

1. Generate special rooms - game start, level boss/challenge, treasure chamber if level = N
   • These rooms have special rules:
   • level boss can't be too close to game start
   • game start must be one of the corners and cannot have a staircase
   • limit to certain number of attempts?
   • no other chests/items/enemies/anything is allowed in the final treasure chamber - only the goal of the game
2. Generate remaining overlapping rooms - rooms cannot be directly adjacent to each other
   • limit to certain number of attempts
   • make sure Room::expand doesn't panic
3. Generate passages between rooms, doorways to rooms
4. Generate locked doors, must ensure that there is at least one path between a downward stairway (stairs coming from below) and the key to that locked room (may involve getting other keys)
   • for the first level, consider the player start position instead of the stairway
5. Generate staircases - need either up, down, or both staircases - should have 2 of each kind scattered far from each other throughout the level
   • staircases cannot block doors to passageways
6. Generate enemy spawn points, pick a random probability of that enemy spawning - in every room except the very first room that the player start position is in
7. Generate special items like new weapons and the level key - different colored chest - cannot be in the start room of the game or in the boss/challenge room
8. Generate chests and crates in rooms and hallways (hallways have fewer things - maybe 0 to 6 things in each depending on the length)

There are weird moving white lines that appear in the rendered empty tiles when the character moves on the game shell. Probably a weird floating point error.

Locked doors should be colored differently (maybe a nice pixel art red?). The room key should also be colored to match.

We need to ensure that we only generate doors that can be reached with a key. It should never become impossible to finish the game if you choose the wrong door to unlock. Choosing the wrong door may make it much harder to win though.

Locked doors should produce a pop-up indicating that they need to be unlocked with a key.

After the first locked door, every other locked door should just pop-up a simpler message like "unlock door with a key? Y N" or "Door is locked" if they don't have a key.

Due to the way the overlapping rooms algorithm works, we end up with this phenominon where you have two layers of walls where some walls are only around empty tiles. See the double layers of walls on the left side of this map:

Notice that the walls that are only around empty tiles could easily be trimmed off and the underlying room could be resized to have a smaller area.

We should display things like HP (Health Points) and maybe (eventually) items in a heads-up display (HUD). This should be rendered on top of the game tiles.

Want to be able to output a debug view of the map that is a rendered image.

Step 1: Refactor: Instead of using indexing and storing default_floor_sprite_index, have an enum to represent different variations of floor tiles. Then, we can look that up from the separate sprite tables for rendering to the screen/rendering to an image. This will completely decouple the map from sprites and we can stop storing the sprite table in the map at all. We should create a helper constructor to create a standard sprite table from a texture id for a spritesheet.

Step 2: add some method to floor map that renders to an image given a filename. Does not need to be efficient. Only for debug purposes.

Step 3: should be able to output a map at any point in the level generation.

We can seed an RNG for every level that needs to be generated and then use rayon to parallelize the generation of all of them.

It would be neat if we could display the enemy's health points in a little bar rendered on top of them (either horizontally or vertically).

Place chests containing items that can be collected and added to the player's inventory in the various rooms.

Same perfect maze generation algorithm as usually (depth-first search), except that the adjacents that are allowed to be searched must satisfy both of these conditions:

1. Tile is not the edge of the room
2. Tile does not have two or more adjacent room floor tiles (if it does then it must be a wall that should not be opened)

The algorithm can either start with a room filled with empty tiles or a room filled with walls. If the room starts empty then the remaining empty tiles at the end should be filled with wall tiles.

• Ice enemies that freeze you
• Metal or rock enemies that can't be defeated by normal weapons
• Enemies that are very fast but weak, or very powerful but slower
• Poisonous or spiky enemies that must be defeated with range weapons (poison slowly kills you over time unless you have an antidote)
• Lasers and spikes and pits
• Enemies that quickly surround you

Should not be able to play game without ever engaging with the enemies.

Mastering weapons and defeating more powerful enemies is going to be one of the main challenging aspects of the game. Doing so will take mastery and that is an important aspect of rougelike games.

Challenge rooms are spawned on every floor and they basically exist to test your mastery of the level. They are not mandatory in that you can complete the game without ever entering a challenge room. (Need to validate for this during level generation.) However completing the game without doing challenge rooms is significantly harder because the advanced items at the end help a lot.

Should be able to almost walk until a challenge room but then leave if you exit fast enough or don't go too far into the room. (i.e. the challenge only activates if you go two tiles in or something) The ground of challenge rooms should always have some special pattern or marking to make it immediately clear.

Idea: a hole or a pit that drops you into the challenge room on the next floor.

One of the staircases in the screenshot below blocks a part of the room. We should check that all items (traversable or not) have a path around them before we place them.

The overall architecture of this game supports many features:

• having multiple distinct, non-overlapping screens - game menu, main game playing mode, end screen, credits, etc.
• having multiple distinct, overlapping screens - game pause menu, inventory, map screen (all interactive -- having their own event handling, main loop, etc.)
  • many of these are specific to the current non-overlapping screen (i.e. pause menu or inventory does not make sense over the game menu)
• a pause state during which the game should not progress (everything appears frozen)
• shared resources across all screens like the SDL2 window, texture_creator, etc.
• screens need to be able to pass input/output back and forth (maybe in the form of actions--each screen should have its own Action enum)
  • confirmation yes/no to a dialog prompt
  • current inventory/equipment info for the inventory screen
  • map + visited info for the map screen

Layers can be implemented by calling the render methods in the relative order of the layers (back to front).

The application main loop keeps track of the currently active non-overlapping screen. That screen has an update method that is called every frame. The update method is given the ability to change to a different screen.

Pressing the B button should result in the player playing an attack animation specific to the direction it is facing. Anything adjacent in that direction with a HealthPoints component should lose some health. (moved: #57)

The player should be able to view their inventory when they pause the game. They should also be able to use items and discard them as well. Moving them around would also be a great feature. (These can be broken up into separate issues if needed)

The game should pause when the inventory is opened.

Remove unwrap() calls that should really be handled properly.

Should have an integration test or something that runs the level generation 1000 times with random map keys to make sure it doesn't panic during that time. Output the map key that failed (or just every map key if that is easier) so it is possible to debug.

Need to know that level generation doesn't fail too often. (May need to increase attempts every once in a while.)

Once we get more validations (e.g. #14, #20) this will also help us know that we aren't breaking any of those invariants.

Also want to somehow test that map generation is deterministic. That is, the same map key produces the same map every time you use it.

We should probably have a top-level src/animations/mod.rs that exports everything that src/map/floor_map/sprite.rs used to contain. The contents of that tile are pretty decoupled from the map so there's really no reason to keep them there. Less nesting is also nice.

Enemies that shoot arrows. Cannons that fire in a fixed pattern. Cannons that come out of the wall. Cannons that fire a shot, turn, then fire another shot.

We should have a benchmark for the amount of time it takes to generate the 10 levels of the game. Use criterion.rs.

There are quite a few big opportunities for optimization that weren't taken for the sake of just getting things working at first. For example we currently regenerate the entire rooms graph every time when we should really only do it once and then keep it up to date. There are lots of such examples throughout the code and someone just needs to put in the effort to think about it.

Sometimes level generation takes an infinite amount of time because something that it is trying to do is actually impossible, regardless of how many times we loop. To fix this, we need to pass in a number of attempts to the MapGenerator and replace our loop statements with limited loops. When we reach the limit, we should return an Err to indicate that something failed. When such an error propagates up, we should use the same rng to generate another MapKey and then try again using that.

A consequence of this strategy is that some MapKeys will actually collide with other MapKeys. Not a huge deal though because we aren't doing cryptograph hashing. It's more important that we actually eventually return a map and do not loop forever.

We should fatally error if 5 MapKeys don't work in succession. That would be a hell of an edge case...

• Arrows - regular, flaming, ice arrows
• Energy bombs - single use, sends out a pulse that pushes all enemies away from you and does a little damage to them all - good for when you're surrounded
• Elemental swords that work better on certain enemies - e.g. fire sword that works better on ice enemies
• Regular bombs - could have enemies that are made of metal so they are quite strong but hard to defeat because your sword does very little damage

Special purple chest that contains new weapons

Holding select pauses the game and brings up a menu that allows you to quickly switch between items with the arrow keys.

Weapons could have different attack mechanics that take time to master. For example a sword that swings out and propels you forward so you hit through the enemy and land on the other side. Or a javelin that stabs outward and pushes enemies a little back when it hits.

Special chests (colored purple and gold) should contain treasure keys. There should be exactly one of these chests on every floor. It's best if these are at the end of some challenge (e.g. #18, #16).

If the gate back to the previous level is setup like below, you will go back and forth between levels over and over again. We can fix this in several ways:

1. Completely stop the player's movements when transitioning between levels
   • Requires clearing the movement queue in the Keyboard system
2. Ensure during level generation that such a scenario is not possible
   • Harder. Should be possible though (maybe?)
3. Add a short Wait component and see if that is not too jarring

There were a lot of problems getting sdl ttf to cross compile onto ARMv7. Would be a good idea to experiment with other things too.

https://github.com/redox-os/rusttype

https://github.com/ggez/ggez/blob/master/src/graphics/text.rs#L350

Would be nice to have a strings.toml file that is included into the game (via include_str!) and then the game pre-rendered all of the text while loading the game.

In the future, we'd want to split that up per level or something once we get a lot of strings. All is good enough for now though.

• Pre-rendering in build.rs to images (See also)
• Using gpu_cache

Sounds for attacking, getting attacked, unlocking doors, ambient music

https://gamedev.stackexchange.com/questions/71530/where-does-event-based-audio-fit-in-a-component-based-entity-system

Idea: a mutable thread safe vector of events/actions passed between systems. This ends up with the SoundEffects System which executes after the other systems that fill this vector. The SoundEffects System uses these events to play sounds. The vector is cleared before every dispatch/update of all the systems.

https://www.libsdl.org/projects/SDL_mixer/

• Door open
• Gate shut
• Attack (sword swipe + different sounds for enemies)
• Hit
• etc.

Gated rooms that are opened by finding and flicking a switch. The switch could be at the end of a maze room (#18) or something.

Should not be able to move during uninterruptable animations like attack/hit. Add a Wait component whenever one of those animations is activated. Should also not be able to attack when Wait is active. Should not be able to change directions while Wait is active

Also, since Wait is created in the Animator, it should also be managed there too instead of in Physics.

Add some basic, low-level enemies to the rooms. Let them walk around randomly (within their rooms) and let them seek and attack the player.

Should enemies be able to attack players standing in a doorway?

Need to add and remove enemy entities when going between levels Not required because of new architecture (#77)

• Play hit animation when enemies are hit

It would be neat if the player could push stone blocks around and stuff. Would require changing the physics engine to accept a mass with each colliding bounding box. We would then only apply a fraction of the full force required to separate the two intersecting rectangles. This force would be proportional to the ratio of their masses.

This requires doing two passes over the objects since the first pass will push some objects halfway and then the second pass will need to push other objects the rest of the way.

The validations module is kind of a code smell. Instead of validating at runtime, we should be forcing the type system to take care of things for us. If Walls can't have objects, then we should change Tile so that they can't have objects. We can do this using an enum that only has tile properties that make sense for each tile.

The TileType representation is also pretty horrendous. Like Room and Door are both technically room tiles. But then so is Wall. Passageway and PassagewayWall are both passage tiles but we don't group them that way. This whole type should not be a flat enum. We should have separate ones for PassageTile and RoomTile.

Related: game map should not store tile size. Should use the tile size of the current level.

Some considerations:

• When deciding on tile sprites, we will need to consider a wholistic representation of "rooms" so that we can scatter things like torches and generate appropriate floor tiling patterns.
• There may be walls within rooms, not just around them or around passages
• Need to know which tiles are part of a given room so we can place objects
• Objects can never block a doorway or go on a wall

Decorate the treasure room with some sprites and chests.

The treasure room should have golden walls. When you go in, there should be a large idol of several golden columns surrounding a golden chest. The front column should have a sign on it. Interacting with the sign explains that this is the final treasure chamber. Only those who are worthy of holding the treasure keys may extract the bounty within. The player is able to "apply" the treasure keys they have collected so far to shrink the columns surrounding the chest. Once they have all 10, the columns should shrink down to zero and the player should be able to collect the golden chest and win the game!

Add a validation for this.

Must ensure that there is some way to get through the game.

This game key results in a starting room with two dead-ends:

21TOEFJiR0Wjd2gnHa8h0Csiap4NjkZnbqzNDT5xwjA

Part of this is validating that you can get from the start of the game to the end of the game somehow.

Should only be one player start room and treasure room in the entire game. Should be one challenge room per level (#16).

We assume that tiles are 16x16, but this tile is 16x22 and anchored at the bottom, not in the center. The anchor parameter of SpriteImage should be taken into account during rendering and we should define the sprite images for these staircases in MapSprites with the correct dimensions.

These are rooms that are completely pitch black except for a small area around the player. Enemies can come surprise attack the player. The player can wake up other enemies with its light. Has to navigate a maze of passages to get through.

This might even be good for a challenge room. Variety comes from the random maze that you have to get through.

Maybe we could put some wood in the room that could be used to light a fire and create light in the room.

Loading screen that shows the progress of map generation. Should update with which phase of map generation we are in.

Within the Interactions system, if the player enters a staircase they should automatically go to the corresponding entry of the next/prev level.

Replace the default wall tiles with appropriate patterns and layouts based on their adjacents and based on the different patterns laid out in the sprite guide for the dungeon spritesheet.

Every room should have doors on every entrance.

Walls within rooms should have torches to light them

If there aren't walls there already, we should surround the staircases with walls. Looks weird otherwise.

In order to make development efficient, we should have our own version of the build-arm script and the corresponding Docker image specifically for this project.

We will also need to cross compile SDL_ttf

We should log the map key to a log file every time. Also log every time we regenerate a key because we ran out of attempts on the previous one. Add the log and env_logger crates.

We only want to render up until what is visible to the player. That is, if they haven't opened a door yet or if a door closes, they should only be able to see up until that. As long as there is a way for the user to get somewhere (i.e. without passing through non-traversable tiles) it should be visible.

We only want the current room/passage to be visible when the player is currently in it. That means that we should figure out which room/passage the camera focus is in, then only render those tiles. Tiles should be rendered below everything else so animations look good.

To model what the character can currently see: a modified ray tracing/flood fill algorithm. Needs to take into account that there should only be a limited view from a passage into a room (no infinite depth of field). Once inside a room that has torches/lights on the walls you should be able to see the entire room. On the other hand, a room without that should be pitch black except a circle around the player.

• Can see up to 2 tiles past an entrance
• When standing in an entrance, can see the entire room that the player is facing but not the room that the player's back is turned to
• Full maps rendered for debugging purposes are still preserved (i.e. all rooms should still show up) - this should be easy because the most straightforward way to implement this is to take the region of tiles within the screen and narrow it even more.
• Fill in invisible space with the empty tile sprite (any tiles that shouldn't be visible are considered invisible)

Inspired by the ice mazes in Pokemon. Randomly generated with enemies to fight or projectiles to get past. Leads to some chests as a reward for mastery.

Maybe we should have different elemental themes for each floor? Question: how to keep interesting on multiple playthroughs? Do not want too much redundancy/predictability.

Wall tiles with an empty tile below them or no tile below them should not receive any wall decorations.

Want to layout the different patterns of floor tile sprites automatically during level generation. This will make the floors look more interesting than just the default floor tile being used now.

See dungeon floors section of spritesheet guide.

Convert the codebase to the 2018 edition.

https://rust-lang-nursery.github.io/edition-guide/rust-2018/index.html