Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

floor/map generation
Started by zettelrhean Oct 01 2018 06:28 AM

14 replies to this topic
lua corona
[TOPIC CONTROLS]
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

i'm trying to make a floor/map generation for a game i'm making, each room can have up to fours doors, one on each wall but i need it to stop generating after a certain point so each floor isn't endless, i've realized that to do this i need each floor to be generated before game play starts and before the next floor is visually loaded for the player to explore, the closest thing i can think of for an example to what i'm trying to do is how the floors or levels are generated in the game "binding of Isaac" i was thinking of using a random number generator to choose how many rooms will be on each floor that means that i need some rooms to be dead ends and one room needs to be guaranteed to be the "boss" room which will lead to the next floor once completed, i also need a way to have the game memorize the rooms and their layout so you can go back to them and not get a entirely new room even if you've explored that room already



[TOPIC: post.html]
#2

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

Sounds like you already have a lot of answers regarding what you need.

Did you have a specific question? :D



[TOPIC: post.html]
#3

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

Well, I'll take a crack at answering one of the questions that I think you need answered and that's random seed based procedural generation. This is something of a special interest of mine and I've created several different systems that use it. I'm too fascinated about this topic to even wait for you to clarify your question(s). :D

As you may know, numbers generated using math.random() aren't really random. The resulting numbers may appear random at a glance, but they are generated using a predetermined code and results from using math.random() will always be the same when run using the same random seed. If you are don't know about how random numbers work in computers, I would really advice googling about them. They are fantastic, if you are a bit weird like me. :D

So, here we get to the cool thing. You can use math.random() to create pseudo random numbers and by controlling the random seed, you can create highly randomised sequences of numbers that will always be the same under specific circumstances. For example, in one of my games, I do the following:

1) Player selects a level and composer moves the player to game.lua.
2) The scene starts by taking the level, n, that the player just selected and calculates it's log+1 value, e.g. level 1: math.log(1+1) = 0.30102999566.
3) The resulting 0.30102999566 is turned to string and the first 9 characters after the dot are picked up separately in a loop that looks something like this:
 

local log = tostring(math.log(n+1))
local g = {}

for i = 1, 9 do
    g[i] = tonumber(log:sub(i+2,i+2))
end

4) Now these 9 integers could be used to create further series, but in this one particular project, they determine things like: the background's colour and style, the level's exterior walls and their shape, as well as other non-critical, almost purely visual elements in the level.

5) In order to ensure that certain elements, like the background colour, did not repeat too often, I also added some special rules that checked the previous two levels and the next level for their colour value. If there was any overlap, I had a rule for assigning a colour value that none of these other levels had (this of course meant that I also needed to check if previous or future levels would also have to use alternate values, etc.).


The thing about this style is that you will always have the specific logarithm values at specific levels, which means that you will always generate the same numbers for the specific levels since they follow the same rules. The same game also uses something along the lines of math.randomseed(math.log(n+n+1)*10000) to create the random seed for each level. I then use this to place assets around the level. Again, the random seed varies greatly between levels. Often times it may be thousands of levels before any repetition. However, the random seed will always be the same for each specific level, which means that they will always be generated the same way.

By using random seed to your advantage like this is the easy part. The challenging part is in actually writing the rules for the procedural generation of the levels. For instance, in your example, you could use the code example that I used in the following way.

1) The first two integers determine a room's width and height.
2) The second two could determine the number of doors and the sides of the floor that they are located on.
3) Then the next ones determine the exact location of the doors, whether they lead somewhere or not, etc. it's all up to you.

If you want to guarantee boss rooms or any other rules, you can simply state in your code that if, for instance, the level's number is divisible by 15, then the floor will have a boss room. Then you could again have other rules for where that room actually is and how it is generated.


The thing is that you have infinite possibilities of how to approach this issue and how to implement it in your game. The best advice that I can give you is to first refine the game's concept and plan for everything that you will need in a level (as well as how to add some content to new levels in future updates, if you plan on releasing such). Once you lock in the rules for creating your levels, it becomes much harder to change them, especially if you have released the game, because any change that you make into the algorithm will affect all of the levels in your game.

Personally, I have a prototype of a game that is technically infinite. It contains a full fledged independent level select (as a scrollable map) that is automatically updated to infinity. This module is actually something that I plan on using in several games of mine, because it just makes level select screens so easy for me :P The prototype part is actual game/level scene, where the game can create unique levels for as long as the player cares to play them. I haven't worked more on it yet, because I am not sold on the idea that people would necessarily like the idea of a game that is automatically generated and keeps on feeding them new levels until they get bored, as that boredom might strike as soon as they realise that the game is infinite and that no developer has actually hand touched those levels. One way of addressing this could be to, perhaps, add some handpicked assets, events, enemies, etc. to each level in addition to the automatic generation. :P

If you'd like to talk more about these kind of things, feel free to message me.


 



 



[TOPIC: post.html]
#4

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

Oh, and I also wanted to add, that sometimes it can be a looooooooot of fun and great value for the players as well if you include some installation specific elements into the random number generation. That way no two players can have the same levels.

For instance, when the game first starts, you could get unix time and system.getTimer(). Take the last 3-5 integers from the unix time (as in 100-10000 range in seconds) and you'll get 3-5 numbers that will change depending on the time that the app was started. Then, with getTimer, you store the initial value when the app starts and then check it again once the game opens the main menu (or similar) for the first time. There is bound to be some variance between how many milliseconds it takes each user's device to load the game, which means that you'll get another set of random numbers.

Getting both of these number sets is guaranteed to land you highly randomised numbers between players. This way every player will have a unique experience with your game and if they ever decide to replay the game, they'll be guaranteed to have another unique playthrough.



[TOPIC: post.html]
#5

xnailbender

[GLOBAL: userInfoPane.html]
xnailbender
  • Contributor

  • 357 posts
  • Corona SDK

XeduR,

 

Thanks for that great tut and really good examples how to utilize the concept.

 

Ideas to ponder...

 

Appreciate the time you put into it!

 

Nail



[TOPIC: post.html]
#6

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

Well, I'll take a crack at answering one of the questions that I think you need answered and that's random seed based procedural generation. This is something of a special interest of mine and I've created several different systems that use it. I'm too fascinated about this topic to even wait for you to clarify your question(s). :D

As you may know, numbers generated using math.random() aren't really random. The resulting numbers may appear random at a glance, but they are generated using a predetermined code and results from using math.random() will always be the same when run using the same random seed. If you are don't know about how random numbers work in computers, I would really advice googling about them. They are fantastic, if you are a bit weird like me. :D

So, here we get to the cool thing. You can use math.random() to create pseudo random numbers and by controlling the random seed, you can create highly randomised sequences of numbers that will always be the same under specific circumstances. For example, in one of my games, I do the following:

1) Player selects a level and composer moves the player to game.lua.
2) The scene starts by taking the level, n, that the player just selected and calculates it's log+1 value, e.g. level 1: math.log(1+1) = 0.30102999566.
3) The resulting 0.30102999566 is turned to string and the first 9 characters after the dot are picked up separately in a loop that looks something like this:
 

local log = tostring(math.log(n+1))
local g = {}

for i = 1, 9 do
    g[i] = tonumber(log:sub(i+2,i+2))
end

4) Now these 9 integers could be used to create further series, but in this one particular project, they determine things like: the background's colour and style, the level's exterior walls and their shape, as well as other non-critical, almost purely visual elements in the level.

5) In order to ensure that certain elements, like the background colour, did not repeat too often, I also added some special rules that checked the previous two levels and the next level for their colour value. If there was any overlap, I had a rule for assigning a colour value that none of these other levels had (this of course meant that I also needed to check if previous or future levels would also have to use alternate values, etc.).


The thing about this style is that you will always have the specific logarithm values at specific levels, which means that you will always generate the same numbers for the specific levels since they follow the same rules. The same game also uses something along the lines of math.randomseed(math.log(n+n+1)*10000) to create the random seed for each level. I then use this to place assets around the level. Again, the random seed varies greatly between levels. Often times it may be thousands of levels before any repetition. However, the random seed will always be the same for each specific level, which means that they will always be generated the same way.

By using random seed to your advantage like this is the easy part. The challenging part is in actually writing the rules for the procedural generation of the levels. For instance, in your example, you could use the code example that I used in the following way.

1) The first two integers determine a room's width and height.
2) The second two could determine the number of doors and the sides of the floor that they are located on.
3) Then the next ones determine the exact location of the doors, whether they lead somewhere or not, etc. it's all up to you.

If you want to guarantee boss rooms or any other rules, you can simply state in your code that if, for instance, the level's number is divisible by 15, then the floor will have a boss room. Then you could again have other rules for where that room actually is and how it is generated.


The thing is that you have infinite possibilities of how to approach this issue and how to implement it in your game. The best advice that I can give you is to first refine the game's concept and plan for everything that you will need in a level (as well as how to add some content to new levels in future updates, if you plan on releasing such). Once you lock in the rules for creating your levels, it becomes much harder to change them, especially if you have released the game, because any change that you make into the algorithm will affect all of the levels in your game.

Personally, I have a prototype of a game that is technically infinite. It contains a full fledged independent level select (as a scrollable map) that is automatically updated to infinity. This module is actually something that I plan on using in several games of mine, because it just makes level select screens so easy for me :P The prototype part is actual game/level scene, where the game can create unique levels for as long as the player cares to play them. I haven't worked more on it yet, because I am not sold on the idea that people would necessarily like the idea of a game that is automatically generated and keeps on feeding them new levels until they get bored, as that boredom might strike as soon as they realise that the game is infinite and that no developer has actually hand touched those levels. One way of addressing this could be to, perhaps, add some handpicked assets, events, enemies, etc. to each level in addition to the automatic generation. :P

If you'd like to talk more about these kind of things, feel free to message me.


 


 

ok so i understand some of this but im in a grade 10 computer science class while im doing this so logarithms are quite complicated to me, although i do understand the seed generation to a point what i need is say the first floor can have between 5 to 10 rooms plus two special rooms that will always appear, i need a way to choose a random number for the room amount (that i can probaly do on my own) but the challenging part for me is making sure that when that limit is reached there arent any doors that lead to nowhere, so what i need is before the player can even move the whole floor has been generated including the two guaranteed rooms, if youd like i can place the code i have so far so you have a better understanding of what im trying to do, although it does rely on outside assets so im not sure how that will work on your end



[TOPIC: post.html]
#7

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

Well, you don't necessarily have to understand how logarithms work specifically in order to do something with them. Just understanding what you can expect the results to be is enough. For instance, try running this piece of code:
 

local iterations = 10

for i = 1, iterations do
	print("math.log("..i..") = "..math.log(i))
end

-- console output:
-- 20:14:13.101  math.log(1) = 0
-- 20:14:13.101  math.log(2) = 0.69314718055995
-- 20:14:13.101  math.log(3) = 1.0986122886681
-- 20:14:13.101  math.log(4) = 1.3862943611199
-- 20:14:13.101  math.log(5) = 1.6094379124341
-- 20:14:13.101  math.log(6) = 1.7917594692281
-- 20:14:13.101  math.log(7) = 1.9459101490553
-- 20:14:13.101  math.log(8) = 2.0794415416798
-- 20:14:13.101  math.log(9) = 2.1972245773362
-- 20:14:13.101  math.log(10) = 2.302585092994

You'll see that logarithm of 1 is 0, but for any other positive number you receive a value that has at least 12 decimals (in those first 10 runs, at least). You'll also see that the first number, i.e. the integer, doesn't actually change all that much, but the numbers after the decimal do. This is where you can pick out those numbers using the code that I demonstrated above and you'll receive a nice random seed between levels, while also guaranteeing that each n level will remain consistent should the player re-enter them.

Please do share your code, so that I (as well as others on the forum) can pitch in and help you work some of your problems out.

Now, without having seen your code, I could already imagine some simple tricks for determining that room count. For instance, if you take my previous code trick and generate the table g, you could then write a rule for g[1] stating that "if g[1] < 2 then" there are 5 rooms, g[1] < 4 would create 6 rooms, etc. since you know that each entry of g can have an integer value between 0 and 9. You could then use the other entries of g to determine how the rooms are connected to each other, say, if g[2] is divisible by 2, then there is a door to the right of the starting room, etc.

While I do mention logarithms in my examples, there are countless methods that you can use to approach creating number sequences. The only thing that you need to keep in mind is that if you want to ensure that when the player, for instance, enters floor X that all of the rooms on the floor remain the same should the player revisit them, then you have to use a random seed for your floor that is based on a constant, like the floor number in your case.



 



[TOPIC: post.html]
#8

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

Well, you don't necessarily have to understand how logarithms work specifically in order to do something with them. Just understanding what you can expect the results to be is enough. For instance, try running this piece of code:
 

local iterations = 10

for i = 1, iterations do
	print("math.log("..i..") = "..math.log(i))
end

-- console output:
-- 20:14:13.101  math.log(1) = 0
-- 20:14:13.101  math.log(2) = 0.69314718055995
-- 20:14:13.101  math.log(3) = 1.0986122886681
-- 20:14:13.101  math.log(4) = 1.3862943611199
-- 20:14:13.101  math.log(5) = 1.6094379124341
-- 20:14:13.101  math.log(6) = 1.7917594692281
-- 20:14:13.101  math.log(7) = 1.9459101490553
-- 20:14:13.101  math.log(8) = 2.0794415416798
-- 20:14:13.101  math.log(9) = 2.1972245773362
-- 20:14:13.101  math.log(10) = 2.302585092994

You'll see that logarithm of 1 is 0, but for any other positive number you receive a value that has at least 12 decimals (in those first 10 runs, at least). You'll also see that the first number, i.e. the integer, doesn't actually change all that much, but the numbers after the decimal do. This is where you can pick out those numbers using the code that I demonstrated above and you'll receive a nice random seed between levels, while also guaranteeing that each n level will remain consistent should the player re-enter them.

Please do share your code, so that I (as well as others on the forum) can pitch in and help you work some of your problems out.

Now, without having seen your code, I could already imagine some simple tricks for determining that room count. For instance, if you take my previous code trick and generate the table g, you could then write a rule for g[1] stating that "if g[1] < 2 then" there are 5 rooms, g[1] < 4 would create 6 rooms, etc. since you know that each entry of g can have an integer value between 0 and 9. You could then use the other entries of g to determine how the rooms are connected to each other, say, if g[2] is divisible by 2, then there is a door to the right of the starting room, etc.

While I do mention logarithms in my examples, there are countless methods that you can use to approach creating number sequences. The only thing that you need to keep in mind is that if you want to ensure that when the player, for instance, enters floor X that all of the rooms on the floor remain the same should the player revisit them, then you have to use a random seed for your floor that is based on a constant, like the floor number in your case.

 

background = display.newImage("background.png")
background.x = 250
background.y = 160
btnStart = display.newImage("button.png")
btnStart.x = 250
btnStart.y = 250
btnStart.xScale = 0.4
btnStart.yScale = 0.2
floorLvl = 0
strStart = "Start"
textTitle = "Dungeon"
textTitle2 = "Delver"
textStart = display.newText(strStart, 250, 250, "SKB.ttf", 36)
textTitle = display.newText(textTitle, 225, 115, "SKB.ttf", 48)
textTitle2 = display.newText(textTitle2, 300, 150, "SKB.ttf", 48)
 
 
 
 
function Start (event)
floorLvl = 1
btnStart.isVisible = false
textStart.isVisible = false
background.isVisible = false
textTitle.isVisible = false
textTitle2.isVisible = false
room = display.newImage("room.png")
room.x = 240
room.y = 160
room.xScale = 1.55
room.yScale = 1.55
sprPlayer = display.newImage("Player.png")
sprPlayer.x = 240
sprPlayer.y = 160
sprPlayer.xScale = 0.5
sprPlayer.yScale = 0.5
 
 
end
function debugEvent (event)
grid = display.newImage("grid.png")
grid.x = 239
grid.y = 160
grid.xScale = 1.099
grid.yScale = 1.4
 
 
end
 
Runtime:addEventListener("key", debugEvent)
btnStart:addEventListener("tap", Start)
 
 
this is what i have currently, ive mostly been working on sprites and setting the groundwork while i learn from you guys, with that said im now thinking i should work on the more basic stuff for example im planning on having it scan the eight grid spots adjacent to the player and if something is occupying that spot it wont let you go there, you can see which tile you can go to because it is supposed to be highlighted if empty, so in other words i guess i need collision but i need it to detect if a space is occupied BEFORE movement not during
 
also i dont know how to show my code like you did so i just copied and pasted it


[TOPIC: post.html]
#9

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 766 posts
  • Corona SDK

ok so i understand some of this but im in a grade 10 computer science class while im doing this so logarithms are quite complicated to me

 

Think of some common bases and their respective powers (b, b2, b3, ...):

 

- Base 2:     2,     4,       8,       16,         32,           64, ...

- Base 10: 10, 100, 1000, 10000, 100000, 1000000, ...

 

In these examples, the base-b logarithm's values are 1, 2, 3, 4, 5, 6, ...

 

In fact, this will be true for any valid base. So, at least in the case of a power, the logarithm means both "how many times was the base multiplied by itself?" (the exponent) but also "which step in the sequence is this?".

 

A code example:

function GetCeilingPowerOf2 (x) -- useful say to find the smallest POT texture where x will fit
  local power = 1 -- 2^0 == 1
  local steps = 0

  while power < x do
   power = 2 * power -- base 2
   steps = steps + 1
  end

  return power, steps -- "steps" is the (base-2, AKA binary) logarithm
end

You can also walk backward through the sequence; to un-multiply a step, you divide by 2. Continuing in this way past step 1 will land you on the value of 1, with logarithm / step 0. You can keep dividing by 2 to get fractional values (1 / 2, 1 / 4, ...) with negative logarithms (-1, -2, ...).

 

If you plot these out, it's pretty evident that a curve would fit nicely between them. This is indeed the case, thus the fractional values. Obviously any intuition about "steps" needs to be stretched here. 

 

There are a number of additional properties (converting powers to coefficients, products to sums, integrating 1 / x, inverting exponentials), but a lot of the aforementioned groundwork can be applied when you get there.

 

The logarithm is particularly interesting in computer science because it's such a flat curve (as listed above, with input 1 million the base-10 version has a value of 6; even with base-2 it's less than 20) and an algorithm or data structure that's logarithm-ish ("divide and conquer" techniques such as a binary search or quick sort being prime examples) will tend to scale well.



[TOPIC: post.html]
#10

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

ok again this is really complicated for me, if possible could it be dumbed down because i just cant wrap my head around all this



[TOPIC: post.html]
#11

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

Well, you don't necessarily have to understand how logarithms work specifically in order to do something with them. Just understanding what you can expect the results to be is enough. For instance, try running this piece of code:
 

local iterations = 10

for i = 1, iterations do
	print("math.log("..i..") = "..math.log(i))
end

-- console output:
-- 20:14:13.101  math.log(1) = 0
-- 20:14:13.101  math.log(2) = 0.69314718055995
-- 20:14:13.101  math.log(3) = 1.0986122886681
-- 20:14:13.101  math.log(4) = 1.3862943611199
-- 20:14:13.101  math.log(5) = 1.6094379124341
-- 20:14:13.101  math.log(6) = 1.7917594692281
-- 20:14:13.101  math.log(7) = 1.9459101490553
-- 20:14:13.101  math.log(8) = 2.0794415416798
-- 20:14:13.101  math.log(9) = 2.1972245773362
-- 20:14:13.101  math.log(10) = 2.302585092994

You'll see that logarithm of 1 is 0, but for any other positive number you receive a value that has at least 12 decimals (in those first 10 runs, at least). You'll also see that the first number, i.e. the integer, doesn't actually change all that much, but the numbers after the decimal do. This is where you can pick out those numbers using the code that I demonstrated above and you'll receive a nice random seed between levels, while also guaranteeing that each n level will remain consistent should the player re-enter them.

Please do share your code, so that I (as well as others on the forum) can pitch in and help you work some of your problems out.

Now, without having seen your code, I could already imagine some simple tricks for determining that room count. For instance, if you take my previous code trick and generate the table g, you could then write a rule for g[1] stating that "if g[1] < 2 then" there are 5 rooms, g[1] < 4 would create 6 rooms, etc. since you know that each entry of g can have an integer value between 0 and 9. You could then use the other entries of g to determine how the rooms are connected to each other, say, if g[2] is divisible by 2, then there is a door to the right of the starting room, etc.

While I do mention logarithms in my examples, there are countless methods that you can use to approach creating number sequences. The only thing that you need to keep in mind is that if you want to ensure that when the player, for instance, enters floor X that all of the rooms on the floor remain the same should the player revisit them, then you have to use a random seed for your floor that is based on a constant, like the floor number in your case.


 

what is G?



[TOPIC: post.html]
#12

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

@zettelrhean, please don't quote my entire responses :D You'll create a highway of duplicate content :D

g refers to the local table g that I created in the code section of my first post

But! To the matter at hand. It really seems that both StarCrunch and I jumped the gun and went a bit overboard with our ideas and implementations. Based on the code that you posted, which you can post as code by pressing the <> code button, it seems that you are just getting the hang of the basics that Lua and Corona SDK have to offer.

You have various means of implementing movement, collision detection, etc. Using Corona's physics engine might be the simplest for collision detection, but it might also be more cumbersome than you really require. For now, I would recommend that you try to tweak around those and get some basic scene together where you can move your character on the screen. Take small steps at a time and learn as you go. Think about the most important gameplay elements in your game and try to implement those first.

In my opinion, the procedural level creation and random seed stuff that I've been talking about isn't something that you should worry about just yet.



[TOPIC: post.html]
#13

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 766 posts
  • Corona SDK

Oh, I didn't mean you had to use any of what I wrote to implement anything.  :) More of a "the logarithm isn't a bunch of random numbers; this is where it comes from" sort of post, in case you wanted some motivation for them.



[TOPIC: post.html]
#14

zettelrhean

[GLOBAL: userInfoPane.html]
zettelrhean
  • Observer

  • 25 posts
  • Corona SDK

ok so i finally implemented movement on a very basic level, next will be doing turns but im just wondering if there is anything else any of you would recommend me doing



[TOPIC: post.html]
#15

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Contributor

  • 361 posts
  • Corona SDK

Well, it really depends on what you want from your game. What do you have now, what do you want the game to do, etc. You need to identify the next key steps for your project and work on those.

It could be moving from on room or level to another (which might require camera system or scene management, etc.) or it could be something entirely different.




[topic_controls]
[/topic_controls]

Also tagged with one or more of these keywords: lua, corona