File indexing completed on 2021-12-21 12:50:22

0001 /*
0002  *  ksokoban - a Sokoban game by KDE
0003  *  Copyright (C) 1998  Anders Widell  <d95-awi@nada.kth.se>
0004  *
0005  *  This program is free software; you can redistribute it and/or modify
0006  *  it under the terms of the GNU General Public License as published by
0007  *  the Free Software Foundation; either version 2 of the License, or
0008  *  (at your option) any later version.
0009  *
0010  *  This program is distributed in the hope that it will be useful,
0011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0013  *  GNU General Public License for more details.
0014  *
0015  *  You should have received a copy of the GNU General Public License
0016  *  along with this program; if not, write to the Free Software
0017  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
0018  */
0019 
0020 //#include <stdio.h>
0021 #include "PathFinder.h"
0022 #include "LevelMap.h"
0023 #include "Queue.h"
0024 #include "Move.h"
0025 
0026 void
0027 PathFinder::BFS (int _x, int _y) {
0028   Queue<int, 10> xq;
0029   Queue<int, 10> yq;
0030   Queue<int, 10> dq;
0031   int x, y, d;
0032 
0033   xq.enqueue (_x);
0034   yq.enqueue (_y);
0035   dq.enqueue (1);
0036 
0037   while (!xq.empty ()) {
0038     x = xq.dequeue ();
0039     y = yq.dequeue ();
0040     d = dq.dequeue ();
0041 
0042     if (x<0 || x>MAX_X || y<0 || y>MAX_Y || dist[y][x]) continue;
0043     dist[y][x] = d;
0044 
0045     xq.enqueue (x);
0046     xq.enqueue (x);
0047     xq.enqueue (x-1);
0048     xq.enqueue (x+1);
0049 
0050     yq.enqueue (y-1);
0051     yq.enqueue (y+1);
0052     yq.enqueue (y);
0053     yq.enqueue (y);
0054 
0055     dq.enqueue (d+1);
0056     dq.enqueue (d+1);
0057     dq.enqueue (d+1);
0058     dq.enqueue (d+1);
0059   }
0060 }
0061 
0062 Move *
0063 PathFinder::search (Map *_map, int _x, int _y) {
0064   int xpos=_map->xpos ();
0065   int ypos=_map->ypos ();
0066   if (xpos == _x && ypos == _y) return nullptr;
0067 
0068   for (int y=0; y<=MAX_Y; y++) {
0069     for (int x=0; x<=MAX_X; x++) {
0070       if (_map->empty (x, y)) dist[y][x] = 0;
0071       else dist[y][x] = PATH_WALL;
0072     }
0073   }
0074 
0075   BFS (_x, _y);
0076 
0077 #if 0
0078   for (int y=0; y<=MAX_Y; y++) {
0079     for (int x=0; x<=MAX_X; x++) {
0080       //if (x==_x && y==_y) {printf ("++ "); continue;}
0081       //if (x==xpos && y==ypos) {printf ("@@ "); continue;}
0082       if (dist[y][x] == PATH_WALL) {printf ("## "); continue;}
0083       printf ("%02d ", dist[y][x]);
0084     }
0085     printf ("\n");
0086   }
0087 #endif
0088 
0089   int d;
0090   Move *move=new Move (xpos, ypos);
0091   int oldX, oldY;
0092   for (;;) {
0093     oldX = xpos;
0094     oldY = ypos;
0095 
0096     if (xpos == _x && ypos == _y) {
0097       move->finish ();
0098       //printf ("move->finish ()\n");
0099       return move;
0100     }
0101 
0102     d = dist[ypos][xpos];
0103 
0104     while (ypos-1 >= 0 && dist[ypos-1][xpos] < d) {
0105       ypos--;
0106       d = dist[ypos][xpos];
0107     }
0108     if (oldY != ypos) {
0109       move->step (xpos, ypos);
0110       //printf ("step (%d, %d)\n", xpos, ypos);
0111       continue;
0112     }
0113 
0114     while (ypos+1 <= MAX_Y && dist[ypos+1][xpos] < d) {
0115       ypos++;
0116       d = dist[ypos][xpos];
0117     }
0118     if (oldY != ypos) {
0119       move->step (xpos, ypos);
0120       //printf ("step (%d, %d)\n", xpos, ypos);
0121       continue;
0122     }
0123 
0124     while (xpos-1 >= 0 && dist[ypos][xpos-1] < d) {
0125       xpos--;
0126       d = dist[ypos][xpos];
0127     }
0128     if (oldX != xpos) {
0129       move->step (xpos, ypos);
0130       //printf ("step (%d, %d)\n", xpos, ypos);
0131       continue;
0132     }
0133 
0134     while (xpos+1 <= MAX_X && dist[ypos][xpos+1] < d) {
0135       xpos++;
0136       d = dist[ypos][xpos];
0137     }
0138     if (oldX != xpos) {
0139       move->step (xpos, ypos);
0140       //printf ("step (%d, %d)\n", xpos, ypos);
0141       continue;
0142     }
0143 
0144     delete move;
0145     return nullptr;
0146   }
0147 }
0148 
0149 Move*
0150 PathFinder::drag(int /* x1 */, int /* y1 */, int /* x2 */, int /* y2 */) {
0151   return nullptr;
0152 }
0153 
0154 bool
0155 PathFinder::canDrag(int /* x */, int /* y */) const {
0156   return false;
0157 }
0158 
0159 bool
0160 PathFinder::canWalkTo(int /* x */, int /* y */) const {
0161   return false;
0162 }
0163 
0164 bool
0165 PathFinder::canDragTo(int /* x */, int /* y */) const {
0166   return false;
0167 }
0168 
0169 void
0170 PathFinder::updatePossibleMoves() {
0171 }
0172 
0173 void
0174 PathFinder::updatePossibleDestinations(int /* x */, int /* y */) {
0175 }
0176