Check if player is able to reach all points

E

Erian

Guest
Hi!

I have searched on Google, but haven't found an answer yet.
I am looking to find a method that I can use in order to find out whether the player can reach all of the point instances that are in the level. I am producing the levels procedurally, so I will have to check whether they can be completed.

The game has a top-down view. The player can move up, down, left and right (not diagonally) and snaps to the square grid. The player can walk everywhere except for through walls, which are 1 square in size. The point items may be placed everywhere, except for on walls.

I have already tried checking which tiles the player can reach. I tried placing an invisible oject on each of the 4 (up, down, left, right) tiles the player can go to from the starting position (i.e. those that don't have a wall on them). I tried to add those instances to an array or list, read the x and y positions from each of the 4 instances and check the 4 squares around them on whether they can be reached. Place an instance on every tile like this untill you can't reach anything anymore. Then check whether all points are on that.

I can't however read the x and y positions from the instances that I stored in the array. I don't want to double check tiles either, which is why I can't simply make two lists, one for y and one for x coordinates. That way I would not be able to check whether a set of coordinates is already in the list.

I also thought about checking whether any walls complete a full enclosure. Problem here is that the outside of the whole level is also enclosed by walls, and that I haven't found a way to deal with branching walls and solid wall rectangles. (i.e. a 2X3 rectangle would not enclose an open space, but does complete a circle)

Are there any simpler methods for doing this? Is there anything in GameMaker already that can do this?
Or does anyone have a suggestion? I'm really stuck.
 

jo-thijs

Member
Hi!

I have searched on Google, but haven't found an answer yet.
I am looking to find a method that I can use in order to find out whether the player can reach all of the point instances that are in the level. I am producing the levels procedurally, so I will have to check whether they can be completed.

The game has a top-down view. The player can move up, down, left and right (not diagonally) and snaps to the square grid. The player can walk everywhere except for through walls, which are 1 square in size. The point items may be placed everywhere, except for on walls.

I have already tried checking which tiles the player can reach. I tried placing an invisible oject on each of the 4 (up, down, left, right) tiles the player can go to from the starting position (i.e. those that don't have a wall on them). I tried to add those instances to an array or list, read the x and y positions from each of the 4 instances and check the 4 squares around them on whether they can be reached. Place an instance on every tile like this untill you can't reach anything anymore. Then check whether all points are on that.

I can't however read the x and y positions from the instances that I stored in the array. I don't want to double check tiles either, which is why I can't simply make two lists, one for y and one for x coordinates. That way I would not be able to check whether a set of coordinates is already in the list.

I also thought about checking whether any walls complete a full enclosure. Problem here is that the outside of the whole level is also enclosed by walls, and that I haven't found a way to deal with branching walls and solid wall rectangles. (i.e. a 2X3 rectangle would not enclose an open space, but does complete a circle)

Are there any simpler methods for doing this? Is there anything in GameMaker already that can do this?
Or does anyone have a suggestion? I'm really stuck.
Hi and welcome to the GMC!

There are multiple ays in achieving this and you were an a good tack.

So first of all, GameMaker has an mp_grid system that finds a path in a tile based system
from a point to a goal and it returns true or false based on whether it found a solution.
Using this has some advantages and disadvantages over what you were trying to do,
but I currently like what you were trying to do more, so I'm not going to describe this method in more detail, unless you want me to.

You tried placing instances of an invisible objects on whereever the player can move to.
You keep track of these instances using an array.
You run in the problem of not being able to read the x and y coordinates of the instances you placed in the array though.

So, I'm not sure why you weren't able to read their x and y coordinates, but this is certainly possible.
However, you don't even need arrays to keep track of the instances.
You could use with structures to loop through all the instances.
With structures work as follows:
suppose you have an object obj_tile and you want the instances of this object to execute some code outside their events,
then you can just simply use this in GameMaker:
Code:
with obj_tile {
    // code to be executed
}
You can now just use this instead of looping through your array.

However this strategy has some efficiency flaws, as you will loop over previously created instances of the invisible object as well.
So, here's yet an even better solution:
just let the invisible object do all the stuff in its create event!
You create 1 instance of the invisible object at the staring position of the player.
In its create event, he checks for a free space in every direction.
If a free space is found, it creates yet another instance of its own object type at that location.
As that instance is created, it executes its own create event before returning to the create event of its creator.
This will pretty efficiently fill the reachable tiles with instances of the invisible object.

However, we can still improve this method by not using this invisible object at all, but instead use a data structure.
With a ds_grid, you can keep track of information of every tile.
You can put a 0 on every empty tile and put a 1 on every tile containing a wall.
You then create a script that takes this grid and the player's coordinates in this grid as arguments.
The script will check if the tile at those coordinates is empty (is 0) and if so, it will write the number 2 to that location to indicate it's reachable.
Then the script calls itself again in recursion for all the neighboring spots.
When the script is done executing, the grid will have a 2 at every reachable location.
You then just have to check the value in the grid at every tile containing a detination point.

You also tried using 2 arrays to represent the invisible objects, 1 containing the x coordinates, the other containing the y coordinates.
However, youcould not check if a new coordinate was already present in these 2 arrays at a previous index.
You could use a for loop to loop through evey index of the 2 arrays and compare every single coordinate with the new one.
However, this would not be efficient.
Instead, you could convert every pair of coordinates (x, y) to a single number as y * grid_width + x.
This will give unique values for every valid coordinate pair.
You can then use ds_map as a set that keeps track of all these numbers (converted from coordinates)
by storing the value 0 under the number as key.
If the ds_map contains that key, you've already dealt with those coordinates before.

You also tried checking wall enclosures.
While this can be used for a solution, it will be a very complicated one
and I don't suspect it will have considerable advantages over the previously discussed methods,
so I'm going to ignore that.

Finally, you're doing all of this to check if a procedurally generated level is completeable,
but isn't it way more logical to make the procedure so that this is always already the case?
Why would you allow the procedural method to generate impossible to complete levels,
then verify they cannot be completed and then just let the same procedure generate a new level
in the hopes of generating a completeable level that time?
Sounds like a very inefficient and undesireable way of doing things.
 
E

Erian

Guest
Thank you for the lengthy response!
That is really helpful.

I could smack myself on the head for not coming up with adding new tiles in the 'create' event. Now that you say it, it seems so glaringly obvious!
But if your method using the ds_grid is more efficient, I might give that a go. I don't want my levels to take ages to load. (the levels aren't big, so they don't, but efficiency is always good)

The reason that I'm checking for this after the level is complete is because I had an even harder time thinking of methods that would avoid creating unsolvable levels. I don't completely regenerate the levels when they are unsolvable. For now, I destroy the point instances that can't be reached. In the end, I either want to move those instances to a new location or change one of the walls so that everything is reachable.

This is the first ever procedural generation game that I'm making, so it is a massive learning project for me.
 
Top