Help with a random maze generator I'm making

Started by Egmundo Huevoz, Sat 20/01/2018 07:09:25

Previous topic - Next topic

Egmundo Huevoz

Skip to the end for my code. Not really necessary to read it, and I don't expect anybody to, since it's long. But I post it just in case.

Hello, everybody. I'm making a maze-generator script, because I searched the forums, and even though there are a few posts about this, there isn't any that helps me (either because I couldn't understand java, or links are down, or some other reason). So I embarked myself on doing one. It's "simple": I use a single room, 4 objects as doors, with appear at random when the player enters/leaves the room. When you interact with the top door, you spawn at the bottom door (I make sure the opposite door always spawns; also at least 1 door). You can look at my script a little bit down, but first, my explanation. I tried to make a function that kept track of the previous room. So:
1) I made a struct with a couple bools (door_up, down, left and right), which turn true if the player interacts with the corresponding door.
2) I combined the struct with an array called Dungeon_room (for now, 100), and also made a global int called dungeon_room_number.
3) Made a bool inside the struct, called been_in_room, which turned true when the player left a room. So if been_in_room was false, I randomized the doors. Otherwise, the doors weren't randomized.
4) I was about to keep writing the script so I could return to the previous room. The doors' locations were being kept by the array (as I knew by some test labels I have), so I just had to make the connection. I probably can do that on my own. But then it hit me. I started imagining an already made maze, and the coming back to previous rooms, and I thought of this situation:



You leave room 1 through the top door, then you go to room 3, and 4, and then... If there happens to be a left door in room 4, and you take it, with my code, you'll just end up in a new room 5, instead of the previous room 1, as you should. I can't figure out HOW to make this happen.



Moreover, If one where to backtrack to room 2, and take a left, he would wound up in room 6, then going down to 7, and going right, instead of back to 1, you would go to room 8... So, I started worrying that maybe I can't solve this with my code. So instead of banging my head against the keyboard for 10 hours searching for a solution that might not exist, I'm posting this here.

In dungeon generator.ash:
Code: ags
struct Stats_dungeon_room{ //dungeon room's stats
  bool door_left;
  bool door_right;
  bool door_up;
  bool door_down;
  bool been_in_room;
};

import Stats_dungeon_room Dungeon_room[100];


In dungeon generator.asc:
Code: ags
Stats_dungeon_room Dungeon_room [100];
export Dungeon_room;


In the dungeon room's script (number 66):
Code: ags

function Spawn (this Object*){ //decides whether or not the door will be visible
  door_spawn=Random(1);
  if (door_spawn==1){
    this.Visible=true;
  }
  else{
    this.Visible=false;
  }
}

function door_randomize(){ //generates 1-4 doors.
  oDown.Spawn();
  oLeft.Spawn();
  oRight.Spawn();
  oUp.Spawn();
  if ((oDown.Visible==false)&&(oUp.Visible==false)&&(oRight.Visible==false)&&(oLeft.Visible==false)){
    door_randomize(); //in case no doors spawn, the function runs again, generatin 1-4 doors.
  }
}

//GRAPHICS

function TopBaseline(this Object*){
  this.Baseline=Game.SpriteHeight[this.Graphic];
}

function door_baselines(){ //guarantees you won't be drawn behind a door
 oDown.TopBaseline();
 oRight.TopBaseline();
 oLeft.TopBaseline();
 oUp.TopBaseline();
}


function walk_to_object(this Object*){ //ensures the player walks to the MIDDLE of the door (instead of it's XY corner)

  if ((this==oLeft)||(this==oRight)){
    door_middle=(this.Y-(Game.SpriteHeight[this.Graphic]/3));
    player.Walk(this.X, door_middle, eBlock);    
  }
  if ((this==oDown)||(this==oUp)){
    door_middle=(this.X+(Game.SpriteWidth[this.Graphic]/2));
    player.Walk(door_middle, this.Y, eBlock);
  }
}

function ChangeroomDoor(this Object*){
  if ((this==oLeft)||(this==oRight)){
    door_middle=(this.Y-(Game.SpriteHeight[this.Graphic]/2));
    player.ChangeRoom(66, this.X, door_middle);
  }
  if ((this==oDown)||(this==oUp)){
    door_middle=(this.X+(Game.SpriteWidth[this.Graphic]/2));
    player.ChangeRoom(66, door_middle, this.Y);
  }
}

function door_create_opposite(){ //guarantees the opposing door will be created (e.g if you entered throught the right door, there will be a left door in the next room
  if (door_entered_left==true){
    oRight.Visible=true;
  }
  if (door_entered_right==true){
    oLeft.Visible=true;
  }
  if (door_entered_down==true){
    oUp.Visible=true;
  }
  if (door_entered_up==true){
    oDown.Visible=true;
  }
}



function Enter(this Object*, Object *opposite_door, String opposite_door_string){
  this.walk_to_object();
  
  opposite_door.ChangeroomDoor();
  
  door_entered_right=false;
  door_entered_left=false;
  door_entered_up=false;
  door_entered_down=false;
  if (opposite_door_string=="left"){
    door_entered_left=true;
  }
  if (opposite_door_string=="right"){
    door_entered_right=true;
  }
  if (opposite_door_string=="up"){
    door_entered_up=true;
  }
  if (opposite_door_string=="down"){
    door_entered_down=true;
  }

}



//SETTING IT UP AND INTERACTIONS



function oRight_AnyClick()
{
 oRight.Enter(oLeft, "right"); 
}

function oLeft_AnyClick()
{
 oLeft.Enter(oRight, "left"); 
}

function oUp_AnyClick()
{
 oUp.Enter(oDown, "up"); 
}

function oDown_AnyClick()
{
 oDown.Enter(oUp, "down"); 
}


function room_Load()
{

  door_baselines();
  door_create_opposite();
  player.SetWalkSpeed(30, 30);
  mouse.Mode=eModeInteract; 
  
  if (Dungeon_room[dungeon_room_number].been_in_room==false){
    door_randomize();
  }
  
  if (Dungeon_room[dungeon_room_number].been_in_room==true){
  dungeon_room_number--;
  }
  
}

function room_Leave()
{

Dungeon_room[dungeon_room_number].door_down=oDown.Visible;  /*AKA current room*/
Dungeon_room[dungeon_room_number].door_up=oUp.Visible;
Dungeon_room[dungeon_room_number].door_left=oLeft.Visible;
Dungeon_room[dungeon_room_number].door_right=oRight.Visible;
Dungeon_room[dungeon_room_number].been_in_room=true;


dungeon_room_number++; //going to the next room, so room 1 turns room 2, etc.
}

function room_FirstLoad()
{
dungeon_room_number=1;
}




Snarky

#1
From a quick skim, I think your issue is that you're not keeping track of the 2D locations of the room overall, so you can't easily work out whether two rooms connect unless you originally went from one to the other.

The solution is to store the locations of the room in 2D coordinates. For example, use your Stats_dungeon_room Dungeon_room [100]; array, but instead of just incrementing the room index (dungeon_room_number) each time you go to a new room, use the x,y position of the room in the dungeon to figure out what the new room index should be (so if you go north or south, the y index should be decremented or incremented, while if you go east or west, the x index should be decremented or incremented):

Code: ags
#define DUNGEON_SIZE 100
#define DUNGEON_DIM_X 10 // the y dimension is DUNGEON_SIZE / DUNGEON_DIM_X

Stats_dungeon_room Dungeon_room[DUNGEON_SIZE];

int dungeonRoomX;
int dungeonRoomY;

int getDungeonIndex(int x, int y)
{
  return x + y*DUNGEON_DIM_X;
}


This way, every time you return to the same location in the dungeon it will have the same room index.

This code gives a 10x10-room dungeon. If you need a somewhat bigger one, e.g. 20x20, the easiest is to just increase the size. If you want it to be massive but sparsely explored there are other ways to store it more efficiently, but it's a little bit more complex.

Egmundo Huevoz

Hey Snarky! Thanks a lot for this. It is indeed what I needed, a 2D "map" of the overall dungeon. I'm ashamed to say the following, but, oh well. I'm still learning. Even though I understand the basic idea of your code, I can't figure out were to put it and exactly how to use it. Maybe if I make 50 trial-an-error attempts, I'll finally figure it out, but I'd rather ask you, if you have the time, if you (or anybody reading this) can explain it to me. I'll be very grateful.
Some other questions:
1) #define is like int, but doesn't take memory, or something like that, right? I only know it from seeing it in a forum post, because the manual, afaik, doesn't mention it. Can you modify them like ints?
2) So, with your code, I make a 10x10 dungeon. If I wanted it to be 20x20, would I have to write this?
Code: ags
#define DUNGEON_SIZE 400
#define DUNGEON_DIM_X 20 

3) If I wanted a random sized dungeon, should I just modify those 2 "defines" again? I can figure out how to do it with ints. I'm assuming it's the same method.
4) When the player reaches the boundaries of the maze, let's say the easternmost room, I should just check if the room's X coordinateequals DUNGEON_DIM_X, and if so, turn the right door invisible?
5) About this line of code:
Code: ags
int getDungeonIndex(int x, int y)
{
  return x + y*DUNGEON_DIM_X;
}

I've never seen that usage of an int before. How does that work? Does x reference "dungeonRoomX"?


I realize I've asked plenty of questions. Feel free to answer whenever you can, if you can. Thanks again.

Snarky

Quote from: Egmundo Huevoz on Sat 20/01/2018 08:42:07
1) #define is like int, but doesn't take memory, or something like that, right? I only know it from seeing it in a forum post, because the manual, afaik, doesn't mention it.

Very roughly. #define defines a macro. It means that on compilation, it replaces every instance of the name you give it with the following string. So it basically means that DUNGEON_SIZE becomes another name for 100. In AGS, it's mainly used to define constants, but you can also put more complicated things in a macro.

QuoteCan you modify them like ints?

No. That's the whole point.

The main reasons to use constants instead of numbers are two:

1. By using meaningful names instead of arbitrary numbers (writing semantic code), the logic of the code becomes easier to follow. Let's say you're looking at a line of code with 100 in it: Why 100? Because that's the size of the dungeon. So just put "dungeon size" instead. Much clearer.
2. If you ever decide to change it, you only have to do it in one place, instead of replacing every instance of 100 in the code with 400 (or whatever). There's no risk of missing one and introducing a difficult-to-find bug.

As a general principle, try to abstract out things that are irrelevant from your code: Should the maze logic depend on the fact that the maze is exactly 100 rooms big? If not, then you shouldn't have that number sprinkled throughout.

Quote2) So, with your code, I make a 10x10 dungeon. If I wanted it to be 20x20, would I have to write this?
Code: ags
#define DUNGEON_SIZE 400
#define DUNGEON_DIM_X 20 

Exactly. And ideally that should be the only change you'd need to make.

Quote3) If I wanted a random sized dungeon, should I just modify those 2 "defines" again? I can figure out how to do it with ints. I'm assuming it's the same method.

You can't do a random size with #define. If you want the size to be random, you need to make the size and dimension int variables, which you initialize to some random value in a function somewhere. You probably still want to have a set max and minimum size, though, and you can set the dungeon array size based on the max possible size.

Quote4) When the player reaches the boundaries of the maze, let's say the easternmost room, I should just check if the room's X coordinateequals DUNGEON_DIM_X, and if so, turn the right door invisible?

Yes, if that's how you want to deal with that case.

Quote5) About this line of code:
Code: ags
int getDungeonIndex(int x, int y)
{
  return x + y*DUNGEON_DIM_X;
}

I've never seen that usage of an int before. How does that work? Does x reference "dungeonRoomX"?

You mean the top line? Well, this is a pretty basic part of programming syntax. It's about how you define a function

int getDungeonIndex() means that getDungeonIndex is a function that returns an int. That means you get a number out of it, and you can call it like:

Code: ags
  int roomIndex = getDungeonIndex(...); // Set roomIndex to the return value of getDungeonIndex(). We have to fill in stuff inside the parenthesis, though
  Dungeon_room[roomIndex].been_in_room = true;


getDungeonIndex(int x, int y) means that it's a function that takes two arguments/parameters, both of them ints. So to call the function, you would have to provide two ints, like this:

Code: ags
  int roomIndex = getDungeonIndex(5, 3);


Or, more likely, this:

Code: ags
  int roomIndex = getDungeonIndex(dungeonRoomX, dungeonRoomY);


In the body of the function, the argument names (x and y) are then replaced by the values we provide (5 and 3 in the first case, or whatever the values of dungeonRoomX and dungeonRoomY are at the time in the second). So getDungeonIndex() performs a calculation on those two values, and returns the result of the calculation. The point of the calculation is to map the 2D map of the rooms into a 1-dimensional array.

Egmundo Huevoz

This is a great explanation, I understood everything now! I'm gonna test this real soon (today I can't) and get back to you. When it works, I'll upload it as a module, crediting you. I don't know how else to repay you, you've been really helpful, I'd even say vital for this part of my project (laugh) Many thanks.
BTW, if I run into a problem, would it be okay to ask you here? I don't want to become a bother.
Cheers! ;-D

Snarky

Great!

Quote from: Egmundo Huevoz on Sat 20/01/2018 20:49:48I don't know how else to repay you, you've been really helpful, I'd even say vital for this part of my project (laugh) Many thanks.
BTW, if I run into a problem, would it be okay to ask you here? I don't want to become a bother.

Don't worry about it: that's what this forum is for. As long as you make an effort to solve it yourself, look in the manual and check if the question has already been answered on the forum first, go ahead and ask.

SMF spam blocked by CleanTalk