Leonhard liebt Labyrinthe

Der Hintergrund

Mein Sohn Leonhard (4 Jahre) liebt Labyrinthe. Ich weiß nicht, woher er Labyrinthe kennt, aber er malt sie und weiß recht gut, wie sie funktionieren:

Labyrinth

Vor kurzem fing er an, ein Spiel aus seinen Gemälden zu machen. Das sind seine Regeln:

ein schwarzes Quadrat kennzeichnet den Startpunkt.
Ein Haken kennzeichnet den Ausgang des Labyrinths (dort werden Sie herausgezogen).
Sie können Kronen sammeln.
Sie können Goldnuggets (die runden Dinge) sammeln.
Sie können einen Weg vor und zurück gehen, aber nicht mehr.
Pfeile können Sie zum Ausgang führen. (Wenn er ein Labyrinth malt, das ich lösen soll, sind sie oft irreführend.)

Kommentierte Version:

blau: Startpunkt
Orange: Kronen
gelb: Bereich mit Goldnuggets
grün: Haken (Ausgang)
pink: Pfeile (meist irreführend)

Kommentiertes Labyrinth

Die Aufgabe

Vielleicht wissen Sie, dass Kinder im Alter von 4 Jahren anfangen, Schweinefleisch zu erzählen, und manchmal befolgt er nicht seine eigenen Regeln, besonders wenn er feststellt, dass er das Ende des Labyrinths nicht mehr erreichen kann.

Hier kommen Sie ins Spiel: Da ich sowieso nach Spielen für Kinder suche , verwandeln Sie seine Idee in ein Spiel, in dem Betrug nicht möglich ist.

Nun, wir brauchen noch einige Definitionen, die ich sagen würde:

Das Spielfeld ist ein n* mRechteck aus gleich großen Quadraten.
Ein Quadrat kann 0 bis 4 Wände haben, eine auf jeder Seite.
Eine Krone ist 50 Punkte wert.
Ein Goldnugget ist 20 Punkte wert.
Wenn Sie auf ein bereits begangenes Feld gehen, wird 1 Punkt abgezogen.
Die Quadrate sind so markiert, dass angegeben wird, wie oft der Spieler darauf gegangen ist (0, 1 oder 2 Mal).
Der Spieler kann in 4 Richtungen gehen, außer wenn es eine Wand gibt.
Eingabegerät kann alles sein. Bitte beachten Sie die Tastaturunterstützung.
Das Labyrinth muss lösbar sein. Das heißt, es muss möglich sein, den Haken vom Startpunkt aus zu erreichen, und es müssen alle Wertsachen gesammelt werden können (auch wenn dies nicht zu einer höchstmöglichen Punktzahl führt).
Wenn der Spieler stecken bleibt, endet das Spiel.
Der Spieler darf nicht sterben, indem er vom Brett fällt. Sie können eine Wand um das gesamte Labyrinth legen oder Kanten umwickeln, was immer Sie möchten.
Das Programm verwendet ein Wortargument (0-65535) als Eingabe. Dies ist der Keim für den Zufallszahlengenerator. Wenn Sie das Programm mit demselben Startwert erneut aufrufen, erhalten Sie dasselbe Labyrinth.

Bonus:

Berechnen Sie die maximalen Punkte, die gesammelt werden können. Bedenken Sie, dass es aufgrund von -1 Punkten möglicherweise besser ist, nicht alle Gegenstände zu sammeln.
Zeige die beste Lösung (kürzester Weg, um maximale Punkte zu bekommen)

Die Regeln

Dies ist ein Beliebtheitswettbewerb, da ich in der Lage sein möchte, den Code zu lesen und zu verstehen und mich vielleicht an neue Ideen meines Sohnes anzupassen. Tut mir leid, Codegolfer, vielleicht möchten Sie eine Kopie dieser Frage mit Regeln erstellen, die besser zum Golfen geeignet sind, z. B. eine Konsolenversion mit allen definierten Zeichen.

Das beliebteste Spiel am 3. Mai wird als Antwort akzeptiert. Und warum nicht in einem App Store veröffentlichen?

popularity-contest game board-game Thomas Weller
quelle

Ich habe das Gefühl, dass dies unter Beschuss geraten könnte, weil es sich um einen zu großen Kunstwettbewerb im Vergleich zu einem Programm handelt. Da sich alle diese Spiele fast identisch verhalten sollten, welchen Grund müsste ich dann für einander stimmen, außer wie schön es aussieht? Es scheint nicht viel Kreativität in diesem Labyrinthspiel zu stecken. Das heißt, ich bin eher ein Golfer, also lasse ich Leute, die häufiger an Pop-Cons teilnehmen, entscheiden, ob dies ein Thema ist.

FryAmTheEggman

Diese Herausforderung besteht aus zwei Teilen: Zum einen dem Labyrinth-Design (es ist jedoch schwierig, algorithmisch ein zufriedenstellendes Spiellabyrinth zu erstellen) und zum anderen der Spiel-Engine (die etwas einfacher ist). Ich denke, es wäre besser, wenn Sie die Herausforderung auf die Spiel-Engine beschränken (und sie zu einem Code-Golf machen würden.) Sie müssten einige Musterlabyrinthe (als Eingabe aus der Textdatei) in der Frage posten (möglicherweise mit Ihrer entworfen) Hilfe des Sohnes.)

Level River St

Verwandte (und möglicherweise ein Teil-Duplikat des Labyrinth-Designteils) codegolf.stackexchange.com/q/25967/15599

Level River St

Ich halte das für eine hervorragende Herausforderung. Es gibt verschiedene Probleme zu lösen und Raum für Kreativität. Weitere Herausforderungen wie diese bitte +1. [Zurück zum Erstellen einer Lösung ...]

Logic Knight

Müssen wir "Pfeile" generieren? Erlauben sie dem Spieler, sie in die andere Richtung zu kreuzen?

TheNumberOne

Antworten:

JavaScript

In Arbeit. Leider ist das Labyrinth nicht immer lösbar - das Limit für den Vor- und Rücklauf ist die eigentliche Hürde.

Edit 1 Cosmetic
Edit 2 Besseres Gameplay, aber das große Problem ist immer noch da

var rows, columns, rowOfs, maze, plPos, points, playing

$('#BNEW').on('click', function() {
    NewMaze();
});
$('#BREP').on('click', function() {
    Start();
});

$(document).on('keydown', function(e) {
    var ok, move, pxy, mz, $td
    switch (e.which)
    {
    case 37:
        (move = -1, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 39:
        (move = 1, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 38: 
        (move = -rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 40: 
        (move = rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    }
    if (playing && ok)
    {
        pxy = getXY(plPos)
        mz = maze[plPos] < 8 ? 8 : 9;
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.addClass("m"+mz);
        maze[plPos] = mz;
        maze[plPos+move] = mz;
        plPos += move*2;
        mz = maze[plPos];
        PTS.value = mz==7 ? points += 20 : mz==6 ? points += 50 : mz == 8 ? points -= 1 : points;
        
        pxy = getXY(plPos)
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.removeClass("m6 m7")
        $('#Player').finish().animate(playerCss(pxy.x,pxy.y));
        CheckEndGame();
    }
    return !move
});

function CheckEndGame()
{
  var msg = ''
  if (maze[plPos] == 5)
  {
      msg = "Maze completed!";
  }
  else if (maze[plPos+1]==9 && maze[plPos-1]==9
        && maze[plPos+rowOfs]==9 && maze[plPos-rowOfs]==9)
  {
      msg = "You are stuck, try again!";
  }
  if (msg) {
    $("#Msg").text(msg).show();
    playing=false
  }
}

function seed(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

function Build()
{
    var i
    var Fill = function(p)
    {
        var d=[rowOfs,-rowOfs,1,-1], i, s, l
        maze[p] = 1
        while(d[0])
        {
            i = random()*d.length|0
            s = d[i]
            if (s != (l=d.pop())) d[i]=l
            if (maze[p+s+s]>8) {
                maze[p+s] = 1, Fill(p+s+s)
            }
        }
    }
    rowOfs = (columns + 1) * 2
    maze = Array(rowOfs * (rows*2+1))
    for (i=0; i < maze.length; i++)
        maze[i] = i % rowOfs? 9 : 0
    Fill(rowOfs+2)
}

function NewMaze()
{
    SEED.value = Math.random()*65536 | 0
    Start()
}
    
function Start()
{
    var sd = SEED.value || 1
    columns = COLS.value |0 || 18
    rows = ROWS.value | 0 || 12
    COLS.value = columns
    ROWS.value = rows
    random = seed(sd)
    PTS.value = points = 0
    $("#Msg").hide();

    Build()
    
    plx = random()*columns|0;
    ply = random()*rows|0;
    setPlayer(plx,ply);
    plPos = getPos(plx,ply);
    BlockTriples(plPos);
    AddItems(plPos);
    Draw();
    playing = true;
  
}

function AddItems(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var cells=[]
    // scan all reachable cells and calc distance from start
    var Go = function(p,l)
    {
        var i,t,mark,r
        ++l
        cells.push([p,l])
            
        maze[p] = 8;
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]<2 && maze[p+t+t]<2) 
            {
                Go(p+t+t, l)
            }
        }
        maze[p] = 0;
    } 
    Go(p,0)
    cells.sort(function(a,b){return a[1]-b[1]})
    cells=cells.slice(10) // cut the shortest distances 
    r = random()*10|0; //exit
    r = cells.length-r-1
    maze[cells[r][0]] = 5;
    console.log(r)
    cells = cells.slice(0,r)
    var ncr = rows, nnu = columns
    for(i = ncr+nnu; i; i--) 
    {
        r = random()*cells.length|0
        maze[cells[r][0]] = (i > ncr ? 7 : 6);
        cells[r] = cells.pop();
    }
    
    
}

function BlockTriples(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var Go = function(p)
    {
        var i,t,size=[0,0,0,0],s=1,nw=0,min,minp
        maze[p] = 8
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]<9 && maze[p+t+t]<8) 
            {
                ++nw
                s += size[i] = Go(p+t+t)
            }
        }
        if (nw > 2) // triple way, block the smallest
        {
            for(i=0,min=1e6; d[i]; i++)
                size[i] && size[i] < min && (min = size[minp = i])
            maze[p + d[minp]] = 5;
        }
        maze[p]=0
        return s
    } 
    Go(p)
}
    
function Draw()
{    
    var q=[], i, x, y;
    for(i = rowOfs+2, y = 0; y < rows; y++)
    {
        q.push('<tr>')
        for (x = 0; x < columns; i += 2, x++)
        {
            tcl = 'm'+(maze[i]|0)       
            maze[i-1]>8 && (tcl += ' wl')
            maze[i+1]>8 && (tcl += ' wr')
            maze[i-rowOfs]>8 && (tcl += ' wu')
            maze[i+rowOfs]>8 && (tcl += ' wb')
            q.push('<td class="'+tcl+'"></td>')
        }
        q.push('</tr>')
        i += rowOfs+2
    }
    $("#TOUT").html(q.join(''));
    $("#Field").show();
}

function setPlayer(posx, posy)
{
    $('#Player').css(playerCss(posx, posy));
}    

function getXY(pos)
{
    return { x: (plPos % rowOfs)/2-1, y: plPos / rowOfs / 2 | 0}
}

function getPos(x, y)
{
   return (x+y*rowOfs)*2 + rowOfs+2;
}

function playerCss(posx, posy)
{
    return{ left: 6+posx*21, top: posy*21+2};
}

input { width: 3em; margin-right:1em }
table { 
  border: 2px solid #000; 
  border-collapse: collapse;
  font-size: 8px }
#Field { 
  margin: 10px; 
  position: relative;
  display: none;
}
td { 
    width: 19px; height: 19px; 
    padding: 0; margin: 0; 
    text-align: center;
}
td.wl { border-left: 2px solid #444; background: #fff }
td.wr { border-right: 2px solid #444; background: #fff }
td.wt { border-top: 2px solid #444;; background: #fff }
td.wb { border-bottom: 2px solid #444; background: #fff }
td.m7 { background: #ffd url(http://i.stack.imgur.com/QUInh.png) -21px 0}
td.m6 { background: #efe url(http://i.stack.imgur.com/QUInh.png) -1px 0}
td.m5 { background: #ddf url(http://i.stack.imgur.com/QUInh.png) -40px 0}
td.m8 { background: #eed }
td.m9 { background: #f55 }
#Player { position: absolute; top:0; left:0; color: #007; background: #fcb; font-size:12px }
#Msg { color: red; font-size:40px; display:none;  }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
ID:<input id=SEED>
Rows:<input id=ROWS>
Columns:<input id=COLS>
<button id=BNEW>New</button>
<button id=BREP>Replay</button>
<div id=Msg></div>
<div id=Field>
<table id=TOUT border=0 cellspacing=0 cellpadding=0>
</table>
<span id=Player>⛄</span>    
</div>
Score: <input readonly id=PTS>

Erweitern Sie das Snippet

edc65
quelle

Gut gemacht, beeindruckend. 👍🏼 Ich verstehe nicht, wie Sie das Labyrinth erstellen. Wie funktioniert dieser Teil?

CousinCocaine

@CousinCocaine Der Build - Funktion Gebrauch eine rekursive Füllung, es ist das mehr ‚klassische‘ Weg , um ein einfach verbundenes Labyrinth zu bauen - siehe en.wikipedia.org/wiki/Maze_generation_algorithm

edc65

Mein Sohn liebt es. Während er möchte, dass ich größere Labyrinthe drucke, spielt er die kleineren online. Nach den Regeln war Ihre Antwort am 3. Mai die beste, also habe ich sie jetzt akzeptiert. Da es auch die einzige Antwort ist, bekommst du das Kopfgeld. Gut gemacht, es ist unglaublich.

Thomas Weller

Vielen Dank, froh, dass es Ihrem Sohn gefällt. Jetzt ist es Zeit, die Gebote zu erhöhen.

edc65

Java

Ich habe mich nie über GolfScript oder CJam beschwert, aber hier ist trotzdem eine Java-Antwort für Sie. Dies war eine wirklich erfreuliche Herausforderung. ;)

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.geom.Ellipse2D;
import java.util.*;
import javax.swing.*;

public class MazeMaker {
    int row, col, exitRow, exitCol, numCells, score, array[][];
    final int SQWIDTH = 20;
    boolean gameOver = true;
    Ellipse2D.Double ellipse;
    JFrame frame;
    JPanel mazePanel;
    JLabel scoreLabel;

    public MazeMaker() {
        frame = new JFrame("Maze");
        frame.setLayout(new BorderLayout());
        JPanel topPanel = createTopPanel();
        frame.add(topPanel,BorderLayout.NORTH);

        createMazePanel();
        frame.add(new JScrollPane(mazePanel),BorderLayout.CENTER);

        setKeyActions();

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
    }

    private void constructArray(int seed, int rows, int cols) {
        array = new int[rows*2-1][cols*2-1];
        for (int[] a : array)
            Arrays.fill(a,-1);
        numCells = (array.length / 2 + 1) * (array[0].length / 2 + 1);
        Random rand = new Random(seed);
        int row = rand.nextInt(array.length / 2 + 1) * 2;
        int col = rand.nextInt(array[0].length / 2 + 1) * 2;
        array[row][col] = 0;
        boolean first = true, a = false, exitFound = false;

        while (true) {
            if (first) {
                int direction = rand.nextInt(4);
                if (direction == 0 && row != 0) {
                    array[row-1][col] = 0;
                    array[row-2][col] = 0;
                    row -= 2;
                    first = false;
                }
                else if (direction == 1 && col != array[0].length - 1) {
                    array[row][col+1] = 0;
                    array[row][col+2] = 0;
                    col += 2;
                    first = false;
                }
                else if (direction == 2 && row != array.length - 1) {
                    array[row+1][col] = 0;
                    array[row+2][col] = 0;
                    row += 2;
                    first = false;
                }
                else if (direction == 3 && col != 0) {
                    array[row][col-1] = 0;
                    array[row][col-2] = 0;
                    col -= 2;
                    first = false;
                }
            }
            else {
                int availableCells = 0;
                boolean up = false, down = false, left = false, right = false;
                if (row != 0 && array[row-2][col] == -1) {
                    availableCells++;
                    up = true;
                }

                if (col != array[0].length-1 && array[row][col+2] == -1) {
                    availableCells++;
                    right = true;
                }

                if (row != array.length-1 && array[row+2][col] == -1) {
                    availableCells++;
                    down = true;
                }

                if (col != 0 && array[row][col-2] == -1) {
                    availableCells++;
                    left = true;
                }

                if (availableCells != 0) {
                    a = true;
                    while (true) {
                        boolean[] b = {up,right,down,left};
                        int i = rand.nextInt(4);
                        if (b[i]) {
                            if (i == 0) {
                                array[row-1][col] = 0;
                                array[row-2][col] = 0;
                                row -= 2;
                            }
                            else if (i == 1) {
                                array[row][col+1] = 0;
                                array[row][col+2] = 0;
                                col += 2;
                            }
                            else if (i == 2) {
                                array[row+1][col] = 0;
                                array[row+2][col] = 0;
                                row += 2;
                            }
                            else if (i == 3) {
                                array[row][col-1] = 0;
                                array[row][col-2] = 0;
                                col -= 2;
                            }
                            break;
                        }
                    }
                }
                else {
                    array[row][col] = 1;
                    if (!exitFound && a) {
                        if (new Random().nextInt(5) == 0) {
                            exitFound = true;
                            exitRow = row;
                            exitCol = col;
                        }
                    }
                    a = false;
                    if (row != 0 && array[row-1][col] == 0 && (array[row-2][col] == 0 || array[row-2][col] == 1)) {
                        array[row-1][col] = 1;
                        array[row-2][col] = 1;
                        row -= 2;
                    }
                    else if (col != array[0].length-1 && array[row][col+1] == 0 && (array[row][col+2] == 0 || array[row][col+2] == 1)) {
                        array[row][col+1] = 1;
                        array[row][col+2] = 1;
                        col += 2;
                    }
                    else if (row != array.length-1 && array[row+1][col] == 0 && (array[row+2][col] == 0 || array[row+2][col] == 1)) {
                        array[row+1][col] = 1;
                        array[row+2][col] = 1;
                        row += 2;
                    }
                    else if (col != 0 && array[row][col-1] == 0 && (array[row][col-2] == 0 || array[row][col-2] == 1)) {
                        array[row][col-1] = 1;
                        array[row][col-2] = 1;
                        col -= 2;
                    }
                }
                if (checkDone()) {
                    if (!exitFound) {
                        exitRow = row;
                        exitCol = col;
                    }
                    break;
                }
            }
        }
    }

    private boolean checkDone() {
        int count = 0;
        for (int k = 0; k < array.length; k+=2) {
            for (int l = 0; l < array[0].length; l+=2) {
                if (array[k][l] == 0 || array[k][l] == 1)
                    count++;
            }
        }
        return count == numCells;
    }

    private JPanel createTopPanel() {
        GridBagLayout l = new GridBagLayout();
        GridBagConstraints c = new GridBagConstraints();
        c.fill = GridBagConstraints.BOTH;

        JPanel panel = new JPanel(l);
        JLabel inputLabel = new JLabel("ID:");
        c.gridwidth = 1;
        l.setConstraints(inputLabel,c);
        panel.add(inputLabel);

        JTextField inputField = new JTextField(5);
        l.setConstraints(inputField,c);
        panel.add(inputField);

        JLabel rowLabel = new JLabel("Rows:");
        l.setConstraints(rowLabel,c);
        panel.add(rowLabel);

        JTextField rowField = new JTextField(3);
        l.setConstraints(rowField,c);
        panel.add(rowField);

        JLabel colLabel = new JLabel("Columns:");
        l.setConstraints(colLabel,c);
        panel.add(colLabel);

        JTextField colField = new JTextField(3);
        l.setConstraints(colField,c);
        panel.add(colField);

        JButton applyButton = new JButton("Apply");
        applyButton.addActionListener(ev -> {
            try {
                int seed = Integer.parseInt(inputField.getText()),
                    rows = Integer.parseInt(rowField.getText()),
                    cols = Integer.parseInt(colField.getText());
                if (seed >= 0 && rows >= 3 && cols >= 3) {
                    gameOver = false;
                    scoreLabel.setText("Score: " + (score = 0));
                    constructArray(seed,rows,cols);
                    row = (int) (Math.random() * (array.length / 2 + 1)) * 2;
                    col = (int) (Math.random() * (array[0].length / 2 + 1)) * 2;
                    frame.setSize((1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 : 750,
                            75+(1+SQWIDTH * array.length)/2);
                    mazePanel.setPreferredSize(new Dimension(
                            (1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 - 15 : 750,
                            15+(1+SQWIDTH * array.length)/2));
                    ellipse = new Ellipse2D.Double(col*SQWIDTH/2+3,row*SQWIDTH/2+3,10,10);
                    setItems();
                    mazePanel.repaint();
                }
            } catch (NumberFormatException ignore) {}
        });
        l.setConstraints(applyButton,c);
        panel.add(applyButton);

        scoreLabel = new JLabel("Score: ");
        c.gridwidth = GridBagConstraints.REMAINDER;
        l.setConstraints(scoreLabel,c);
        panel.add(scoreLabel);

        return panel;
    }

    private void createMazePanel() {
        mazePanel = new JPanel() {
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                int x = 0, y = 0;
                if (!gameOver) {
                    for (int k = 0; k < array.length; k+=2) {
                        for (int l = 0; l < array[0].length; l+=2) {
                            int n = array[k][l];
                            if (n == 0 || n == 1 || n == 4 || n == 5 || n == 6)
                                g.setColor(Color.white);
                            else if (n == 2)
                                g.setColor(Color.green);
                            else if (n == 3)
                                g.setColor(Color.red);
                            g.fillRect(x, y, SQWIDTH, SQWIDTH);
                            if (n == 4) {
                                g.setColor(new Color(245,209,34));
                                g.fillOval(x+3, y+3, 10, 10);
                            }
                            else if (n == 5) {
                                g.setColor(new Color(255,223,55));
                                g.fillPolygon(new int[]{x,x+3,x+8,x+13,x+16,x+14,x+2},new int[]{y+2,y+6,y+2,y+6,y+2,y+16,y+16},7);
                                g.setColor(new Color(12,234,44));
                                g.fillOval(x+7,y+6,4,7);
                            }
                            else if (n == 6) {
                                Graphics2D g2 = (Graphics2D) g.create();
                                g2.setStroke(new BasicStroke(2,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
                                g2.setColor(new Color(108,225,119));
                                g2.drawOval(x+5, y+1, 8, 8);
                                g2.drawLine(x+5, y+3, x+5, y+11);
                                g2.drawArc(x+5, y+8, 7, 7, 180, 180);
                            }
                            g.setColor(Color.black);
                            if (k != array.length-1 && array[k+1][l] == -1)
                                g.fillRect(x-3, y+SQWIDTH-3, SQWIDTH+3, 3);
                            if (l != array[0].length-1 && array[k][l+1] == -1)
                                g.fillRect(x+SQWIDTH-3,y,3,SQWIDTH);
                            x += SQWIDTH;
                        }
                        x = 0;
                        y += SQWIDTH;
                    }
                    g.setColor(Color.red);
                    ((Graphics2D) g).fill(ellipse);
                }
            }
        };
    }

    private void setKeyActions() {
        InputMap im = mazePanel.getInputMap(JComponent.WHEN_IN_FOCUSED_WINDOW);
        ActionMap am = mazePanel.getActionMap();

        im.put(KeyStroke.getKeyStroke("pressed UP"), "up");
        am.put("up", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != 0 && array[row-1][col] != -1 && array[row-2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed RIGHT"), "right");
        am.put("right",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != array[0].length-1 && array[row][col+1] != -1 && array[row][col+2] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed DOWN"), "down");
        am.put("down", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != array.length-1 && array[row+1][col] != -1 && array[row+2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed LEFT"), "left");
        am.put("left",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != 0 && array[row][col-1] != -1 && array[row][col-2] != -1 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });
    }

    private void setItems() {
        array[exitRow][exitCol] = 6;
        Random r = new Random();
        for (int k = 1; k < (array.length * array[0].length) / 20; k++) {
            int row = r.nextInt(array.length / 2 + 1) * 2,
                col = r.nextInt(array[0].length / 2 + 1) * 2;
            if ((row == this.row && col == this.col) || array[row][col] == 4 || array[row][col] == 5 || array[row][col] == 6)
                k--;
            else
                array[row][col] = r.nextInt(2) + 4;
        }
    }

    private boolean checkGameOver() {
        if (row == 0 && col == 0)
            return (array[row+2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col+1] == -1);
        else if (row == 0 && col == array[0].length-1)
            return (array[row+2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1);
        else if (row == array.length-1 && col == 0)
            return (array[row-2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col+1] == -1);
        else if (row == array.length-1 && col == array[0].length-1)
            return (array[row-2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1);
        else if (row == 0)
            return (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == 0)
            return (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else if (row == array.length-1)
            return (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == array[0].length-1)
            return (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else
            return (array[row-2][col] == 3 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(MazeMaker::new);
    }
}

Der Prozess der Erstellung des eigentlichen Labyrinths nutzt die Tiefensuchalgorithmus verwendet , jedoch mit einem iterativen Ansatz. So funktioniert das.

Wir beginnen mit einem 2D-Array von intWerten, wobei jedes Element ein -1 ist. Ein zufälliges Element mit geraden Indizes wird ausgewählt und sein Wert wird zu 0:

-1 -1 -1 -1 -1 -1  0 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1

Dann tritt das Programm in eine Schleife ein und prüft auf verfügbare Zellen, bis es einen Zustand erreicht, in dem keine verfügbaren Zellen mehr vorhanden sind. Dies kann mehrmals vorkommen und ist der Zeitpunkt, an dem das Zurückverfolgen beginnt. Zu diesem Zeitpunkt werden alle Nullen, auf die es stößt, zu Einsen. Auch in dieser Zeit wird festgelegt, ob an dieser Stelle ein Ausgang platziert werden soll. Am Ende könnte das Array also so aussehen:

 0  0  0  0  0  0  1  1  1 
 0 -1 -1 -1 -1 -1  0 -1  1 
 0  0  0  0  0 -1  0 -1  1 
-1 -1 -1 -1 -1 -1  0 -1  1 
 0  0  0  0  0  0  0 -1  1 
 0 -1 -1 -1 -1 -1 -1 -1  1 
 0 -1  1  1  1  1  1 -1  1 
 0 -1  1 -1  1 -1 -1 -1  1 
 0 -1  1 -1  1  1  1  1  1

Wenn an bestimmten Stellen im Array eine vorgegebene Anzahl von Einsen oder Nullen vorliegt, wird die Schleife beendet. Mit dem Array wird dann das resultierende Labyrinth gezeichnet:

Resultierendes Labyrinth

Es ist leicht zu erkennen, dass die -1s im Array Wände darstellen und die 0s und 1s Korridore sind. Gegenstände werden zufällig im Labyrinth verteilt. Die rote Ellipse ist der "Spieler", den Sie steuern.

Das Labyrinth ist zur Vereinfachung in ein Bildlauffenster eingebettet. Wenn die Größe des Rahmens die maximale Größe überschreitet, können Sie einen Bildlauf durchführen, um den Rest des Labyrinths anzuzeigen.

Ich würde sagen, das einzige Problem dabei ist, wie der Spielende-Check durchgeführt wird. Ich dachte über mehrere Möglichkeiten nach, um das zu tun, aber schließlich habe ich alles hart programmiert. Ich bin offen für Vorschläge, wie es gemacht werden kann.

TNT
quelle

Dies wird nicht kompiliert.

MazeMaker.java:168: error: cannot find symbol         printArray();         ^   symbol:   method printArray()   location: class MazeMaker

edc65

@ edc65 Danke, dass du mich informiert hast. Ich hatte eine Methode namens printArray, mit der ich das Array ausgegeben habe, habe es aber gelöscht und vergessen, den Methodenaufruf zu entfernen.

TNT

Ok, ich habe es jetzt laufen. Es ist schön. Ich versuche, dasselbe Labyrinth mit derselben ID neu zu starten, aber es scheint nicht zu funktionieren.

edc65

Ich habe es so, dass die Start- und Endposition bei jedem Drücken der Apply-Taste zufällig gewählt werden, aber das Layout des Labyrinths bleibt gleich. Sollte es nicht so sein?

TNT

Ich dachte, das wäre ein Weg, um mit genau der gleichen Herausforderung von vorne zu beginnen. Mein Hauptanliegen ist es zu überprüfen, ob die Herausforderung immer lösbar ist (eine Einschränkung der ursprünglichen Frage, die ich schwer fand)

edc65

Python

Mir ist klar, dass ich zu spät zur Party komme, aber hier ist meine Einstellung zu dieser Herausforderung. Ich ging textbasiert vor, da ich noch nicht dazu gekommen bin, Pygame zu lernen. Es ist Python 3. Ändern Sie die Eingabe in raw_input und es sollte auch in python2 funktionieren.

Der Haken (Ausgang) wird durch "J" dargestellt. "W" ist Kronen (50). "G" ist Goldnuggets (20). Der Spieler ist "O". Ich habe mit der Verwendung von "P" für den Player experimentiert, aber ich fand "O" leichter zu identifizieren.

Ich habe die erste Labyrinthgeneration mit Standardtiefe verwendet und dann Gold, Kronen, Haken und die aktuelle Spielerposition hinzugefügt. Ich habe die Kriterien, nach denen alle Schätze erhältlich sind, nicht umgesetzt. Screenshot des Labyrinthspiels

import random

direcs = {'n':[0,-1],
          's':[0,1],
          'w':[-1,0],
          'e':[1,0]}
dirs = ['n','s','e','w']

class maze_space(object):
    def __init__(self):
        self.n = 0
        self.s = 0
        self.e = 0
        self.w = 0
        self.visited = 0
        self.contents = ' '

    def mirror(self,drct,val):
        if drct == 'n' : self.s = val
        if drct == 's' : self.n = val
        if drct == 'e' : self.w = val
        if drct == 'w' : self.e = val

class MazeGame(object):

    def __init__(self,horiz=12,vert=8):
        self.completed = 0
        self.score = 0
        self.grid = [[maze_space() for x in range(horiz)] for y in range(vert)]

        def walk(y,x):
            self.grid[y][x].visited = 1
            drs = self.make_dir_list(y, x)
            random.shuffle(drs)
            for dr in drs:
                yy = y + direcs[dr][1]
                xx = x + direcs[dr][0]
                if not self.grid[yy][xx].visited:
                    setattr(self.grid[y][x], dr, 1)
                    self.grid[yy][xx].mirror(dr, 1)
                    walk(yy, xx)

        y, x = self.pick_row_col()
        walk(y, x)
        self.maze_populate()
        self.printmaze()

    def main_loop(self):
        while not self.completed:
            move = get_move(self.grid, self.cury, self.curx)
            self.make_move(move)
            self.printmaze()

    def pick_row_col(self):
        '''pick a random cell in the grid'''
        row = random.randint(0, len(self.grid) - 1)
        col = random.randint(0, len(self.grid[0]) - 1)
        return row, col

    def make_dir_list(self, y, x):
        '''return list of available move directions'''
        drs = dirs[:]
        if x == 0 : drs.pop(drs.index('w'))
        if y == 0 : drs.pop(drs.index('n'))
        if x == len(self.grid[0]) - 1 : drs.pop(drs.index('e'))
        if y == len(self.grid) - 1 : drs.pop(drs.index('s'))
        return drs

    def maze_populate(self):
        # populate maze with crowns and gold nuggets
        for treasure in ['G', 'W']:
            for _ in range(random.randint(1, len(self.grid[0]))):
                yy, xx = self.pick_row_col()
                self.grid[yy][xx].contents = treasure

        self.cury, self.curx = self.pick_row_col() # start position
        exity, exitx = self.pick_row_col() # hook (exit) position
        #make sure start is not on top of exit
        while self.cury == exity and self.curx == exitx :
            exitx = random.randint(0, len(self.grid[0]) - 1)

        self.grid[self.cury][self.curx].contents = 'O'
        self.grid[exity][exitx].contents = 'J'

    def make_move(self,dr):
        self.grid[self.cury][self.curx].visited += 1
        self.grid[self.cury][self.curx].contents = '.'
            # player has walked twice -> disable
        if self.grid[self.cury][self.curx].visited >= 3:
            self.grid[self.cury][self.curx].contents = 'X'
            drs = self.make_dir_list(self.cury, self.curx)
            for d in drs:
                yyy = self.cury + direcs[d][1]
                xxx = self.curx + direcs[d][0]
                self.grid[yyy][xxx].mirror(d,0)

        yy = self.cury + direcs[dr][1]
        xx = self.curx + direcs[dr][0]
        if self.grid[yy][xx].contents == 'J': self.completed = 1
        if self.grid[yy][xx].contents == 'W': self.score += 50
        if self.grid[yy][xx].contents == 'G': self.score += 20
        if self.grid[yy][xx].contents == '.': self.score -= 1
        self.grid[yy][xx].contents = 'O'
        self.cury, self.curx = yy, xx

    def printmaze(self):
        if self.completed: print('\nMaze complete.  Good job!')
        print('Score: %d'%self.score)
        print('|'+''.join('---' for _ in self.grid[0]))
        for line in self.grid:
            print('|' + ''.join(' %s '%x.contents if x.e else ' %s|'%
                                x.contents for x in line))
            print('|' + ''.join('  -' if x.s else '---' for x in line))

def get_params():
    hor = input('width (default=12): ')
    hor = int(hor) if hor else 12
    ver = input('height (default=8): ')
    ver = int(ver) if ver else 8
    rseed = input('seed : ')
    rseed = int(rseed) if rseed else random.randint(1,65535)
    print(rseed)
    random.seed(rseed)
    print("'J' = hook (exit)\n'O' = Player")
    print("'G' = gold nugget (20 points)\n'W' = Crown (50 points)")
    print('Player may only tread on a given tile twice')
    return hor,ver

def get_move(grid, y, x):
    choice = input('where do you want to move %s q to quit: '%dirs)
    if choice == 'q' : exit()
    if choice in dirs and getattr(grid[y][x],choice): return choice
    return get_move(grid, y, x)

def main():
    hor,ver = get_params()
    maze = MazeGame(hor,ver)
    maze.main_loop()

if __name__ == '__main__':
    main()

Alan Hoover
quelle