Is this risky?

[Ziphold]

I'm working on a rogue like dungeon explorer game where the rooms are pre-made but when the player walks through the door to enter a new room, It's randomly chosen from the variety of different rooms.
The problem was that often times, same rooms would be selected, so I had to write the following code to fix that:

This is the code: (I changed the variable names for simplicity, this code WORKS)

       do {
         alreadyBeenInThatRoom = 0;
         chosenRoom= irandom(array_length_1d(roomList)-1);
         for(i=0; i<100; i++) {
             if listOfVisitedRooms[i] = chosenRoom {
                 alreadyBeenInThatRoom= 1;
                 break;
              }
          }
       } until alreadyBeenInThatRoom = 0;
       room_goto(chosenRoom);

As you can see, what I do is select a room from the array of available rooms. I then check if I were in that room previously (All those rooms player visited are written in the array.) This list would be cleared every 5-10 rooms so there would always be a match the computer could find.

But is this really the optimal solution? What if someone's computer goes on a streak of selecting already visited rooms over and over again? The game would freeze for a second or two until the non-visited room is selected?

Any recommendations or ideas?
In advance, thank you.

 

[Geoff Jones]

Theoretically possible but I guess it depends on how gamemaker processes the "do, while until" functions. Does it process what's in between the do and until at the roomspeed? Or does it use the CPU's full processing power? I dunno.. I'd like to know the answer to that! In either case, I don't think you have much to worry about.

 

[Ziphold]

Theoretically possible but I guess it depends on how gamemaker processes the "do, while until" functions. Does it process what's in between the do and until at the roomspeed? Or does it use the CPU's full processing power? I dunno.. I'd like to know the answer to that! In either case, I don't think you have much to worry about.

Yeah, I think so too. I will play around with it a bit more.

 

[Nocturne]

The loop would need to go through the check thousands of times before it would be noticeable to the player, so I wouldn't worry too much about the possibility (the loop is processed in a single step). What I would say though, is that you'd be better of creating a ds_list and then just removing those rooms that are visited and when the list is empty regenerate it. So you'd have something like:

Create ds list and add 10 rooms
Shuffle the list
Go to the first room on the list
Remove list entry [0] (list now has 9 items only)
Repeat while checking if the list is empty
If the list is empty, start again (repopulate, shuffle, delete one at a time)

Hope that helps!

 

[Ziphold]

The loop would need to go through the check thousands of times before it would be noticeable to the player, so I wouldn't worry too much about the possibility (the loop is processed in a single step). What I would say though, is that you'd be better of creating a ds_list and then just removing those rooms that are visited and when the list is empty regenerate it. So you'd have something like:

Create ds list and add 10 rooms
Shuffle the list
Go to the first room on the list
Remove list entry [0] (list now has 9 items only)
Repeat while checking if the list is empty
If the list is empty, start again (repopulate, shuffle, delete one at a time)

Hope that helps!

Great idea, not so hard to implement! Thank you!

 

[Geoff Jones]

I calculated the odds. Theres about a 1 in 1,000,000,000,000,000,000,000,000,000,000 chance of the player having to wait 1 second if the roomspeed is 30 and the number of rooms in the list is 10... for that to happen, there would have to be some kind of glitch in the matrix.

 

[TheouAegis]

But hiccups would be quite noticeable and quite common. The smaller the room population, the more likely hiccups will occur. That's why a shuffled list is preferred in GM.

 

[zendraw]

you can just shuffle the list, this way you can also save the order of the rooms.

 

[GMWolf]

Problem with list shuffling is that you will get some horrible (relatively speaking) performance during that step. It's a fair number of read and writes. Not only that but on large populations, you may get cache misses.
It probably won't matter unless you have millions of entries, and GM probably doesn't do memory allocation too well for cache prediction optimizations to matter, but here is what I think would be a more efficient implementation:

var possible_rooms = [];
foreach(room in rooms) {
     if (room not visited) {
        possible_rooms <- room
    }
}

var n = irandom(possible_rooms.length);

room = possible_rooms[i];

This is, of course, heavy pseudo code but I think you get the idea.


Whatever the case, to optimize any technique you may be using, do have an array of visited rooms.
Instead, have a map of rooms, to visited booleans.
Then, realize that all rooms are indexed from 0 to N-1, and use an array instead.

This means you cna do

//testing
if (visited[room]) {
  //do something
}

//setting
visited[room] = true;

not pseudo code (just dont use the 'room' variable name)

using this, the above psuedo code becomes:

var possible_rooms = []; //array of possible rooms to go to
var size = 0; //size of possible_rooms
//add all unvisited rooms
for(var _room = 0; room_exists(_room); i++) { //loop through each room
    if !visited[_room] {
        possible_rooms[size++] = _room; //Add _room to the end (increments size)
    }
}

var n = irandom(size - 1); //get the random index

room = possible_rooms[i]; //The result

 

[Tornado]

I just noticed a weird thing about ds_list: you cannot access an element at some position! (but you can replace an element at certain position, which is basically the same procedure)

maybe you can try this (no shuffle involved). it is pseuo-code:

DEFINITIONS:
 allRoomsDSMap = {
{0, rm_Room1},
{1, rm_Room2},
{2, rm_Room3},
{3, rm_Room3},
{4, rm_Room5},
{5, rm_Room6},
{6, rm_Room7},
{7, rm_Room8},
{8, rm_Room9},
{9, rm_Room10},
};

allRoomsDSList = {0,1,2,3,4,5,6,7,8,9};
notVisitedRoomsDSList = allRoomsDSList;

CODE TO BE CALLED FOR FINDING NEXT ROOM:
if (notVisitedRoomsDSList.size() > 0) {
    var chosenRoomIndex = irandom(notVisitedRoomsDSList.size());
    ds_list_delete(notVisitedRoomsDSList, chosenRoomIndex);
    room_goto(ds_map_find_value(allRoomsDSMap, chosenRoomIndex));

}
else {
    alert "all rooms already visited"
}

AND WHEN YOU WANT TO RESET IT AGAIN TO HAVE ALL ROOMS:
notVisitedRoomsDSList = allRoomsDSList;

 

[elementbound]

I calculated the odds. Theres about a 1 in 1,000,000,000,000,000,000,000,000,000,000 chance of the player having to wait 1 second if the roomspeed is 30 and the number of rooms in the list is 10... for that to happen, there would have to be some kind of glitch in the matrix.

A small thing I wanna add: loops are not processed at room speed and are not broken down into multiple steps, so it basically uses "full" CPU power ( depending on target your code is interpreted which means additional bookkeeping, but nothing to worry about at this scale ). You can do this by putting a lengthy loop in your room start code or a create event, something like a for(var i =0; i < 1024*1024; ++i)

But your point stands, I would not worry about hiccups before writing the code.

Also, to be honest, I don't get the amount of microoptimization going on in this topic. Unless you have actually measured that the first solution ( pick a random room until you get one that wasn't visited ) is slow, I would not worry about it. But hey, the shuffle method is also nice, but again, unless it is slow in your case ( for example, you have 2^24 rooms to shuffle ), I would not bother.

tl;dr: if you have a solution that works perfectly fine, why come up with more?

 

[TheouAegis]

I'm not really microoptimising with the shuffle list method, it's a method I adopted because the do-until-not-repeated random loop has been noticeably slow over and over and over and can be super slow at times, whereas the shuffled list has been only slow in extreme cases. But yeah, it will just look like the computer farted in either case most of the time; but once the fart is too big, people will suspect something is horribly wrong.