How to calculate precisely the camera position in a maze in order to avoid the walls?

Hello !
I wanted to apply what I learned in Python language starting the following project : creating a 3D maze where I can move and rotate.
I used Python 3.6.1 with PyOpengl on Windows 7 environnement.

Find below some infos :
The walls are made with cubes using glVertex3f.
The Y coordinate of each cube is null --> the cubes are located in the plan (X,Z)
The cubes coordinates are declared as follow :

lab_cubes = [(1,1),(1,3),(2,3),(3,1),(3,2)] # this is a example

The idea is to move the camera and avoid crossing the walls.

I’ve started from a position (with glTranslatef). For each move, I make a translation with a 0.05 step.
I tried to deduct a camera step but I didn’t succeed precisely so I could not deduct the walls position very well.
I assume that I should have used something more ‘mathematics’ !

I don’t know if what I want to do can be made easily.

I don’t know either if my explanations were very clear so find the code below…

import os
import sys
import math
import pygame
from pygame.locals import *
from OpenGL.GL import *
from OpenGL.GLU import *
 
#----------------------------------------------------
# Classe Cube
#----------------------------------------------------
class Cube:
    def __init__(self, vertices, pos=(0,0,0)):
        x,y,z = pos
        self.verts =[[x+X/2,y+Y/2,z+Z/2] for X,Y,Z in vertices]
 
#----------------------------------------------------
# Classe Labyrinthe
#----------------------------------------------------
class Labyrinthe:
 
    # Variables de classe
    vertices = ((1, -1, -1), (1, 1, -1), (-1, 1, -1), (-1, -1, -1), (1, -1, 1), (1, 1, 1), (-1, -1, 1), (-1, 1, 1))
    surfaces = ((0,1,2,3), (3,2,7,6), (6,7,5,4), (4,5,1,0), (1,5,7,2), (4,0,3,6))
 
    def __init__(self):        
        # Définition des textures
        self.texture_sol = self.loadTexture("sol")
        self.texture_cube = self.loadTexture("cube")
 
    def setVerticesLab(self, lab_points, lab_width, lab_height):
        self.points = [(x,y) for x,y in lab_points]
        self.cubes = [Cube(Labyrinthe.vertices, (x,0,-z)) for x,z in lab_points]        
        self.ground_vertices = ((0,-0.1,-(lab_width+1)), (0,-0.1,lab_height+3),(lab_width+1,-0.1,lab_height+3),(lab_width+1,-0.1,-(lab_width+1)))
 
    def loadTexture(self,pstr_obj):
        if pstr_obj == "sol":textureSurface = pygame.image.load('fond_sol4.jpg')
        elif pstr_obj == "cube":textureSurface = pygame.image.load('fond_cube2.jpg')
        textureData = pygame.image.tostring(textureSurface, "RGBA", 1)
        width = textureSurface.get_width()
        height = textureSurface.get_height()
        texid = glGenTextures(1)
        glBindTexture(GL_TEXTURE_2D,texid)
        glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT)
        glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT)
        glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST)
        glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST)
        glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, width, height, 0, GL_RGBA, GL_UNSIGNED_BYTE, textureData)
        return texid
 
    def drawLab(self):
 
        glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)
 
        # On inhibe ce que l'on ne va pas utiliser afin d'accélérer le traitement
        glDisable(GL_FOG) # on ne calcule pas le brouillard
        glDisable(GL_LIGHTING) # on ne calcule pas l'illumination
        glDisable(GL_COLOR_MATERIAL) # on ne calcule pas les couleurs        
 
        # Affichage du sol
        glEnable(GL_TEXTURE_2D)
        glBindTexture(GL_TEXTURE_2D, self.texture_sol)        
        glBegin(GL_QUADS)
        for vertex in self.ground_vertices:
            glTexCoord2f(0.0, 0.0); glVertex3f(self.ground_vertices[0][0],self.ground_vertices[0][1],self.ground_vertices[0][2])
            glTexCoord2f(1.0, 0.0); glVertex3f(self.ground_vertices[1][0],self.ground_vertices[1][1],self.ground_vertices[1][2])
            glTexCoord2f(1.0, 1.0); glVertex3f(self.ground_vertices[2][0],self.ground_vertices[2][1],self.ground_vertices[2][2])
            glTexCoord2f(0.0, 1.0); glVertex3f(self.ground_vertices[3][0],self.ground_vertices[3][1],self.ground_vertices[3][2])
        glEnd()
 
        # Affichage du labyrinthe
        glEnable(GL_DEPTH_TEST) # pour éliminer les faces cachées
        glDepthFunc(GL_LESS) 
        glEnable(GL_TEXTURE_2D)
        glBindTexture(GL_TEXTURE_2D, self.texture_cube)
 
        for each_cube in self.cubes:        
            glBegin(GL_QUADS)        
            for surface in Labyrinthe.surfaces:
                glTexCoord2f(0.0, 0.0); glVertex3f(each_cube.verts[surface[0]][0], each_cube.verts[surface[0]][1], each_cube.verts[surface[0]][2])
                glTexCoord2f(1.0, 0.0); glVertex3f(each_cube.verts[surface[1]][0], each_cube.verts[surface[1]][1], each_cube.verts[surface[1]][2])
                glTexCoord2f(1.0, 1.0); glVertex3f(each_cube.verts[surface[2]][0], each_cube.verts[surface[2]][1], each_cube.verts[surface[2]][2])
                glTexCoord2f(0.0, 1.0); glVertex3f(each_cube.verts[surface[3]][0], each_cube.verts[surface[3]][1], each_cube.verts[surface[3]][2])
            glEnd()
 
        pygame.display.flip()    
 
#----------------------------------------------------
# Classe Camera
#----------------------------------------------------
class Camera:
    def __init__(self, lab, pos=(0,0,0), rot=(0,0,0,0)):
        self.pos = list(pos) 
        self.offsetMove = 0.05 # pas de déplacement en translation dans la scène
        self.offsetMoveCam = 0.068 # pas de déplacement de la caméra définit empiriquement
 
        # Définition de la position réelle
        self.xpos = pos[0]
        self.ypos = pos[2]
 
        # Définition de la position affichée
        self.translate(pos[0], pos[1], pos[2])
 
        # Définition du labyrinthe
        self.lab = lab
        self.printPosCam()
 
    def printPosCam(self):
        pos_cur = glGetDoublev(GL_MODELVIEW_MATRIX)
        camera = pos_cur[3]
 
    def events(self,event):
        if event.type == pygame.MOUSEBUTTONDOWN:
            if event.button == 4:
                self.translate(0,0,1.0);self.lab.drawLab()                
            elif event.button == 5:
                self.translate(0,0,-1.0);self.lab.drawLab()
        elif event.type == pygame.MOUSEMOTION:
            xcam, ycam = event.rel
            # on prévoie ici de faire une rotation de la scène
 
    def _defRealPos(self,pos):
        # Conversion de la valeur de la position dans la labyrinthe
        # en coordonnée 'labyrinthe'
        # ****************
        # *** PROBLÈME ***
        # ****************
        return(pos)
 
    def checkPos(self, xp, yp):
        # On vérifie que la position n'est pas sur un mur
        return (xp, yp) not in self.lab.points
 
    def update(self, dt, key):
        if key[pygame.K_LEFT]:
            xp = self._defRealPos(self.pos[0]+self.offsetMoveCam)
            if self.checkPos(-xp,self.ypos):
                self.xpos = -xp;
                self.translate(self.offsetMove,0,0)
                self.pos[0]+=self.offsetMoveCam
                self.lab.drawLab()
        elif key[pygame.K_RIGHT]:
            xp = self._defRealPos(self.pos[0]-self.offsetMoveCam)
            if self.checkPos(-xp,self.ypos):
                self.xpos = -xp;
                self.translate(-self.offsetMove,0,0)
                self.pos[0]-=self.offsetMoveCam
                self.lab.drawLab()
        elif key[pygame.K_UP]:
            yp = self._defRealPos(self.pos[2]+self.offsetMoveCam)
            if self.checkPos(-self.xpos,yp):
                self.ypos = yp;
                self.translate(0,0,self.offsetMove)
                self.pos[2]+=self.offsetMoveCam
                self.lab.drawLab()
        elif key[pygame.K_DOWN]:
            yp = self._defRealPos(self.pos[2]-self.offsetMoveCam)
            if self.checkPos(-self.xpos,yp):
                self.ypos = yp
                self.translate(0,0,-self.offsetMove)
                self.pos[2]-=self.offsetMoveCam;
                self.lab.drawLab()
 
    def translate(self,x,y,z):        
        glTranslatef(x,y,z)        
 
    def rotate(self,angle, x, y, z):
        # Rotation autour d'un axe (x ou y ou z 1 si rotation 0 sinon) avec un angle
        # Pas encore utilisé
        glRotatef(angle, x, y, z)
 
#----------------------------------------------------
# Programme principal
#----------------------------------------------------
pygame.init()
display = (800,600)
pygame.display.set_mode(display, DOUBLEBUF|OPENGL|OPENGLBLIT)
os.environ['SLD_VIDEO_CENTERED'] = '1'
pygame.display.set_caption('Labyrinthe 3D')
gluPerspective(45, (display[0]/display[1]), 0.1, 50.0)
pygame.event.get();
pygame.mouse.get_rel()
clock=pygame.time.Clock()
 
# Définition du labyrinthe
#lab_cubes = [(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,5),(3,1),(3,5),(4,1),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
#lab_cubes = [(1,1),(1,3),(2,3),(3,1),(3,2)]
#lab_cubes = [(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,5),(3,1),(3,5),(4,1),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
#lab_cubes = [(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)]
lab_cubes = [(1,2),(1,3),(1,4),(1,5),(2,2),(3,1),(3,4),(3,5),(4,3),(4,4),(5,1),(5,2),(5,3)]
lab = Labyrinthe()
 
# Position initiale de la caméra 
#cam = Camera(lab,(-3, 0, 2), (0, 0, 0, 0))
#cam = Camera(lab,(-2, 0, 2), (0, 0, 0, 0))
#cam = Camera(lab,(-3, 0, 3), (0, 0, 0, 0))
#cam = Camera(lab,(-2, 0, 2), (0, 0, 0, 0))
cam = Camera(lab,(-4, 0, 1), (0, 0, 0, 0))
 
lab.setVerticesLab(lab_cubes,5,5) # param 2 et 3 pour le sol
lab.drawLab()
 
# Boucle sur l'attente d'une touche pressée
while True:
    dt = clock.tick()/3000
    for event in pygame.event.get():
        if event.type == pygame.QUIT:pygame.quit();sys.exit()
        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE:
                pygame.quit(); sys.exit()
        cam.events(event)
 
    key = pygame.key.get_pressed()
    cam.update(dt, key)
 
pygame.quit()
quit()

Does someone tell me how to do it easily ?
My next problem to solve is to make a rotation. I tried some ways (translate + Y axe rotate) but I did not achieve.

Thanks in advance for your answers !

I haven’t looked into your code (too lazy ), but lets talk about how you can approach this:

When I understood you correctly, you have basically a 2d maze. Yes it is rendered in 3d, but if you camera can just move forward, backward, left and right and not up and down it is a 2d problem, since you are moving in a plane. Then only 2 coordinates are relevant, the ones that describe the cameras movement ( I think X and Z in your case).
Now your cubes have a location and a volume which they occupy. In 2d this volume is represented by a rectangle. Assuming that your Camera has no volume itself, it is represented by a point. All you need to do now is to check if the current movement of your camera will navigate the point inside one of the rectangles of your cubes. If yes, don’t add the movement to your cameras position. This can also be done in a full 3d maze where you can move in all 3 dimensions, but the collision checks get more complicated, especially if you start using different kind of wall shapes.

Hint: Add a little offset to the rectangles size while making the collision check. This way you avoid the rare case, that your movement will put you directly onto the border. If that happens you can see through the wall, destroying the illusion of moving through a maze.

Regarding your rotation question… well I don’t know how it is done in the old fixed function pipeline of OpenGL you are using but generally you need to multiply all your objects with a rotation matrix (ask wikipedia about that). You also need to apply this rotation matrix to your movement if you want that hitting the forward key results in a movement into the direction you are currently viewing.

Greetings

[QUOTE=ProgrammerX;1291017]I haven’t looked into your code (too lazy ), but lets talk about how you can approach this:

When I understood you correctly, you have basically a 2d maze. Yes it is rendered in 3d, but if you camera can just move forward, backward, left and right and not up and down it is a 2d problem, since you are moving in a plane. Then only 2 coordinates are relevant, the ones that describe the cameras movement ( I think X and Z in your case).
Now your cubes have a location and a volume which they occupy. In 2d this volume is represented by a rectangle. Assuming that your Camera has no volume itself, it is represented by a point. All you need to do now is to check if the current movement of your camera will navigate the point inside one of the rectangles of your cubes. If yes, don’t add the movement to your cameras position. This can also be done in a full 3d maze where you can move in all 3 dimensions, but the collision checks get more complicated, especially if you start using different kind of wall shapes.

Hint: Add a little offset to the rectangles size while making the collision check. This way you avoid the rare case, that your movement will put you directly onto the border. If that happens you can see through the wall, destroying the illusion of moving through a maze.

Regarding your rotation question… well I don’t know how it is done in the old fixed function pipeline of OpenGL you are using but generally you need to multiply all your objects with a rotation matrix (ask wikipedia about that). You also need to apply this rotation matrix to your movement if you want that hitting the forward key results in a movement into the direction you are currently viewing.

Greetings[/QUOTE]

Hello !
Thanks for your reply…
In fact, it’s a 3D maze without Y coordinate, so yes, it can be assimilate to a 2D maze rendered in 3D. I will implement a rotation only around Y axis later.
You can run my code to see the rendering. I’ve attached the two files for the textures…to be put in the current folder.
I tried to do what you said : “…check if the current movement of your camera will navigate the point inside one of the rectangles of your cubes…” and I used also an offset but sometimes it worked, sometimes not.
For the rotation, can I use the function rotatef ?
Do you have example of code which can help me to solve my problem ?
Thanks in advance for your help.

For the collision stuff have a look into this recent thread:

For the rotation, can I use the function rotatef ?
Do you have example of code which can help me to solve my problem ?

Can’t tell you if the mentioned function will do it since I am working with shader programs and own matrix classes. I have no experience with older OGL stuff.

I guess you you should probably read the basics about matrices and vectors. Applying a rotation to an object using matrices is quiet simple and you can use libraries as glm that already provide all you need. For example, you can tell glm to create you a rotation matrix with a specific angle around a desired axis. If all your objects vertices are stored as vectors (not std::vectors ), all you need to do is something like this:

auto RotationMatrix = SomeGLMFuncion();

myClass ObjectOriginal;
... fill with vertices that are of the GLM Vector type

myClass ObjectRotated;

assert(ObjectRotated.numVertices == ObjectOriginal.numVertices);

for (int i=0; i : i < ObjectOriginal.numVertices; ++i)
{
    ObjectRotated.Vertices[i] = RotationMatrix *  ObjectOriginal.Vertices[i];
}

If you want to do more advanced computer graphics stuff, you won’t get around understanding matrices and vectors, since nearly everything is based on them. So better start now.