Java maze game-- How to not go through the wall

Question

So for a class project, I'm making a solvable maze game (in Java). I can randomly generate and display the maze without a problem, and the same goes for the user/player's representation. However, the problem I'm having is with the individual walls of the maze.

I need to make sure that the player can't go through the walls. I've looked around, and it seems a lot of people have similar problems, but they are using a grid structure to make their mazes. I'm not --my maze's walls are just lines, so I can't do what everybody else is doing, (just see if a certain cell in the maze is already occupied --I don't have cells to check).

What I do have is both end points of the line --the starting x, starting y, ending x, and ending y-- and the current point of the upper left corner of the circle that represents the player. I also have the point of the proposed new upper left corner of the circle.

I need to know if the player is going to cross any of the lines that represent walls. At the moment, I loop through an array that contains all of the walls. Given the current player position and proposed player position, I need to find out if that involves crossing a wall. Any tips/hints/help would be much appreciated. Thank you in advance!

Answer 1

Assuming your world is 2D,

[] [] []|[]
      -----
[] [] [] []

[] [] [] []

[] [] [] []

and | and --- are walls

Method #1: enlarge your grid to include the wall intersections. So the size of the row and columns will be row+(row-1),col+(col-1)

this is your new array representation: Original row = 4, new row = 4+3 = 7. This will also create walls to check for diagonal movements.

[ ][ ][ ][ ][ ][|][ ]
[ ][ ][ ][ ][-][-][-]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

Method #2: using the 4x4 representation, create a wall class that stores the adjacent tiles coordinate. And after that create a list to store a list of walls.

Wall(Point x,Point y); // constructor
Wall wall1 = new Wall(new Point(0,2),new Point(0,3));
Wall wall2 = new Wall(new Point(0,2),new Point(1,2));
Wall wall3 = new Wall(new Point(0,3),new Point(1,3));

this representation, allows you to create rules such that 0,0 can go to 1,1 but 0,1 cannot go to 1,0. If you want a unidirectional wall, which might sound silly but who knows? You can modify your wall class constructor:

Wall(Point from,Point to);

Collision checking for method 1: when moving your character, after you move, if it lands on the wall, don't allow the movement.

Collision checking for method 2: when moving your character, cache where the character is from, and where the character will move to if the move is allowed, construct a new Wall object base on that and check if the Wall list contains the new Wall object.

Answer 2

You can construct a line segment (x1, x2), where x1 is the player's current position, and x2 is the location the player is attempting to move to. Any move through a wall would have this line segment intersect the wall segment. You can therefore validate a move by checking (x1, x2) for intersection against all maze walls (a linear-time task).

Checking segment intersection is easy, and there is a nice answer explaining how to implement it.

If you can add any additional information (for example maximum length of walls), you can store the maze in such a way that you would not have to query all walls for intersection. For example, if walls are either horizontal or vertical, and moves are as well, you need only check horizontal walls in case of a vertical move.

Hope this helps!