Un petit Labyrinthe

Comparons les langages de programmation avec l'implémentation d'algo...

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Le petit Labyrinthe

Bien le bonjour, je vous propose un exercice si vous voulez bien :D . Le but de cet exercice est simple : Générer un labyrinthe avec le langage que vous voulez.

Comment générer le labyrinthe ?

Nombreux sont les algorithmes permettant de générer un labyrinthe. A vous de choisir celui qui vous parait le mieux (personnellement je préfère l'exploration exhaustive).

Comment présenter son labyrinthe ?

Votre message devra comporter:

  • Le langage de programmation utilisé
  • Les sources (directement dans le message ou par lien)
  • Le résultat (si possible 2 images l'une qui montre le labyrinthe et l'autre avec la solution du labyrinthe affichée)

Exemple :

  • Langage : Python
  • Sources : Ici
  • Résultat :

Image utilisateur Image utilisateur

+2 -0

Sujet super intéressant ! il est juste dommage qu'il soit proposé à la fi des vacances scolaires, je n'aurais malheureusement surement pas le temps de m'y mettre :'( dommage une autre fois peut être ! PS : Avec quel algo est créé le labyrinthe que tu as mis dans ton post ? C'est assez tarabiscoté pour ressembler à de la fusion aléatoire mais en même temps j'ai cru comprendre que tu préférais le parcours exhaustif !

+0 -0
Auteur du sujet

L'algo utilisé est l'exploration exhaustive :D . Mais même si le principe des 2 algos est différents, le résultat est souvent très ressemblant. Je sais que c'est dommage d'avoir posté ce sujet à la fin des vacances mais rien ne t’empêchera de la faire pendant les vacances de Noël :D .

+0 -0
Staff

Salut,

amusant, j'ai fait ça il n'y a pas longtemps avec lua (en utilisant love), avec exploration exhaustive un peu modifié pour avoir des ponts, et surtout, je repars de la première case visitée au lieu de la dernière, ça donne des branches plus ramifiées.

Après, question jouabilité, les cases qu'on a visitées disparaissent au fur-et-à-mesure.

Les labyrinthes générés ressemblent à ça (j'ai désactivé la disparition pour le screen, bien sûr ^^ ) :

maze

Quand on joue avec la disparition, ça donne un truc dans le genre :

maze2

Voici le code en deux fichiers.

  • main.lua

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
function love.update(dt)
    local mc = maze[playerCell]
    if love.keyboard.isDown('left') and x==xT and yT==y
        and ((not onVbridge and mc.linked.left) or onHbridge) then
        xT=xT-dx
        playerCell = playerCell - 1
        onHbridge = (mc.linked.left ~= mc.left) and (not onHbridge)
    elseif love.keyboard.isDown('right') and x==xT and yT==y 
        and ((not onVbridge and mc.linked.right) or onHbridge) then
        xT=xT+dx
        playerCell = playerCell + 1
        onHbridge = (mc.linked.right ~= mc.right) and (not onHbridge)
    elseif love.keyboard.isDown('up') and y==yT and xT==x 
        and ((not onHbridge and mc.linked.up) or onVbridge) then
        yT=yT-dy
        playerCell = playerCell - nx
        onVbridge = (mc.linked.up ~= mc.up) and (not onVbridge)
    elseif love.keyboard.isDown('down') and y==yT and xT==x 
        and ((not onHbridge and mc.linked.down) or onVbridge) then
        yT=yT+dy
        playerCell = playerCell + nx
        onVbridge = (mc.linked.down ~= mc.down) and (not onVbridge)
    end

    if math.abs(x-xT)<1 and math.abs(y-yT)<1 then
        x=xT
        y=yT
    else
        x=x+(xT-x)*30*dt
        y=y+(yT-y)*30*dt
    end
    if onVbridge or onHbridge then
        plate:set(idh, hero, 0, 0, 0, 0, 0)
        plate:set(idhb, hero, x, y)
    else
        plate:set(idhb, hero, 0, 0, 0, 0, 0)
        plate:set(idh, hero, x, y)
    end
    if playerCell == nx * nz then finished = true end
end

function love.load()
    require('Maze')
    love.window.setTitle('Amazing maze')
    love.mouse.setVisible(false)
    local sprites = love.graphics.newImage('sprites/digital.png')
    local spSize = sprites:getDimensions() / 5

    local sp = {}
    for x = 0, 4 do
        for y = 0, 2 do
            sp[(x+1)+y*5] = love.graphics.newQuad(x*spSize, y*spSize, 
                spSize, spSize, sprites:getDimensions())
        end
    end
    hero = love.graphics.newQuad(2*spSize, 3*spSize, spSize, spSize,
        sprites:getDimensions())
    local bridgeH = love.graphics.newQuad(0, 3*spSize, spSize, spSize,
        sprites:getDimensions())
    local bridgeV = love.graphics.newQuad(spSize, 3*spSize, spSize, spSize,
        sprites:getDimensions())

    local width = 10
    local height = 10
    function initMaze(w, h)
        nx = w or 10
        nz = h or 10
        love.window.setMode(nx*spSize, nz*spSize)
        maze = Maze:new(nx,nz)
        finished = false
        tLastVisit = {}
        for i = 1, nx*nz do
            tLastVisit[i]=0
        end
        x=0
        y=0
        xT=0
        yT=0
        dx=spSize
        dy=spSize
        playerCell = 1
        plate = love.graphics.newSpriteBatch(sprites)
        plate:setBufferSize(2*nx*nz)
        for cell = 1, nx * nz do
            local cellScore = 0
            local mc = maze[cell]

            if mc.linked.left then
                cellScore = 1 end
            if mc.linked.down then
                cellScore = cellScore + 2 end
            if mc.linked.right then
                cellScore = cellScore + 4 end
            if mc.linked.up then
                cellScore = cellScore + 8 end

            local x = (cell - 1) % nx
            local y = (cell - x - 1) / nx
            plate:add(sp[cellScore], x*spSize, y*spSize)
        end

        idh = plate:add(hero, 0, 0)

        for cell = 1, nx * nz do
            local mc = maze[cell]
            local x = (cell - 1) % nx
            local y = (cell - x - 1) / nx
            if mc.up and mc.down and mc.up.linked.down == mc.down then
                plate:add(bridgeV, x*spSize, y*spSize)
            elseif mc.left and mc.right and mc.left.linked.right == mc.right then
                plate:add(bridgeH, x*spSize, y*spSize)
            end
        end

        idhb = plate:add(hero, 0, 0)

        onVbridge = false
        onHbridge = false
    end

    function love.resize(w, h)
        love.window.setMode(nx*spSize, nz*spSize, {resizable=false})
    end

    function love.keyreleased(key)
        if key=='h' and width>10 then
            width = width-5
            initMaze(width, height)
        elseif key=='l' and width<50 then
            width = width+5
            initMaze(width, height)
        elseif key=='k' and height>10 then
            height = height-5
            initMaze(width, height)
        elseif key=='j' and height<50 then
            height = height+5
            initMaze(width, height)
        end
        if key=='right' and finished then initMaze(width, height) end
    end

    function mask(x, y, trsp)
        love.graphics.setColor(0, 0, 0, trsp)
        love.graphics.rectangle('fill', x*spSize, y*spSize, spSize, spSize)
        love.graphics.setColor(255, 255, 255, 255)
    end

    initMaze(width, height)
end

function love.draw()
    love.graphics.draw(plate) 
    time = love.timer.getTime()
    tLastVisit[playerCell] = time
    for i = 1, nx*nz do
        local x = (i - 1) % nx
        local y = (i - x - 1) / nx
        etrsp = (time-tLastVisit[i])*255/10
        mask(x, y, (etrsp < 255 and etrsp or 255 ))
    end
end

  • Maze.lua

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
Maze = {}
function Maze:new(nx, nz)
    local maze = {}
    maze.nx = nx or 10
    maze.nz = nz or 10
    setmetatable(maze, self)
    self.__index = self
    maze:compute()
    return maze
end

function Maze:compute()
    --[[
    Maze generation with a backtracking
    depth-first search algorithm, but
    using a FIFO stack instead of a
    LIFO one. Bridge over existing
    corridors are allowed.
    --]]

    local freeCells = self.nx*self.nz
    math.randomseed(os.time())
    local otherDir = {up='down', down='up', right='left', left='right'}

    for i = 1, freeCells do
        self[i] = {}
        self[i].free = true
        self[i].linked = {}
    end

    for i = 1, freeCells do
        self[i].up    = self[i-self.nx]
        self[i].down  = self[i+self.nx]
        if (i-1)%self.nx ~= 0 then
            self[i].left  = self[i-1]
        end
        if i%self.nx ~= 0 then
            self[i].right = self[i+1]
        end
    end
    self[freeCells].up.down = nil
    self[freeCells].up = nil

    local stackCells = {first=0,last=-1} -- definition of the FIFO stack
    function stackCells.push(val)
        stackCells.last = stackCells.last+1
        stackCells[stackCells.last] = val
    end
    function stackCells.pop()
        val = stackCells[stackCells.first]
        stackCells[stackCells.first] = nil
        stackCells.first = stackCells.first+1
        return val
    end

    local neighbor = {} -- contains reachable neighbors
    function neighbor.append(cell)
        neighbor[#neighbor+1] = cell
    end
    function neighbor.pick()
        return neighbor[math.random(#neighbor)]
    end
    function neighbor.clear()
        for ind = 1, #neighbor do
            neighbor[ind] = nil
        end
    end
    function neighbor.isFilled()
        return #neighbor ~= 0
    end

    -- here begins the serious stuff
    local currentCell = self[1]
    currentCell.free = false
    freeCells = freeCells-1
    while freeCells~=0 do
        -- make a list of accessible neighbors
        neighbor.clear()
        for direc, other in pairs(otherDir) do
            -- close neighbors
            local cell = currentCell[direc]
            if cell and cell.free then
                neighbor.append{direc, cell}
            end
            -- neighbors which are reachable with a bridge
            local cell2 = cell and cell[direc]
            if cell2 and not cell.free and cell2.free and
                not cell.linked[direc] and
                not cell.linked[other] then
                neighbor.append{direc, cell2}
            end
        end

        if neighbor.isFilled() then
            -- choose a neighbor
            local nb = neighbor.pick()
            local dir = nb[1]
            local nbCell = nb[2]
            -- make the link
            currentCell.linked[dir] = nbCell
            nbCell.linked[otherDir[dir]] = currentCell
            -- chosen neighbor become current cell
            stackCells.push(currentCell)
            currentCell = nb[2]
            currentCell.free = false
            freeCells = freeCells-1
        else
            -- if no reachable neighbor,
            -- go open a new way
            -- from a previous cell
            currentCell = stackCells.pop()
        end
    end
end

Et enfin, l'image utilisée pour les sprites :

sprites

Pour l'instant, l'utilisation d'une image pour les sprites peut paraitre overkill, mais l'idée est d'ajouter ensuite une gestion des sprites histoire de pouvoir créer son propre thème pour le labyrinthe. Il faut probablement retravailler un peu le code qui est un peu sale, et l'aspect graphique également. J'ai encore un peu de boulot sur ce projet, donc. :p

Édité par adri1

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+1 -0

Hello, exercice bien sympa :) voici mon code en C implémentant l'algo de fusion aléatoire pour la création du labyrinthe et l'algo BFS pour la recherche du chemin entre 2 cellules.

La récupération des paramètres se fait sur l'entrée standard, ex pour générer un labyrinthe au format html de 400 lignes x 200 colonnes et rechercher le chemin de la cellule 1,1 à la cellule 400,200, il faut saisir

400 200 1,1 400,200 2 (*)

(*) Format de sortie: 0 = aucune, 1 = texte, 2 = html

Exemple au format html

EDIT: Optimisation du programme (utilisation structure union/find), création de fonctions externes pour la partie html, utilisation du rand Mersenne/Twister.

Édité par fromvega

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte