summaryrefslogtreecommitdiffstats
path: root/ksokoban/PathFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'ksokoban/PathFinder.cpp')
-rw-r--r--ksokoban/PathFinder.cpp176
1 files changed, 176 insertions, 0 deletions
diff --git a/ksokoban/PathFinder.cpp b/ksokoban/PathFinder.cpp
new file mode 100644
index 00000000..a7d8bd4d
--- /dev/null
+++ b/ksokoban/PathFinder.cpp
@@ -0,0 +1,176 @@
+/*
+ * ksokoban - a Sokoban game for KDE
+ * Copyright (C) 1998 Anders Widell <d95-awi@nada.kth.se>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+//#include <stdio.h>
+#include "PathFinder.h"
+#include "LevelMap.h"
+#include "Queue.h"
+#include "Move.h"
+
+void
+PathFinder::BFS (int _x, int _y) {
+ Queue<int, 10> xq;
+ Queue<int, 10> yq;
+ Queue<int, 10> dq;
+ int x, y, d;
+
+ xq.enqueue (_x);
+ yq.enqueue (_y);
+ dq.enqueue (1);
+
+ while (!xq.empty ()) {
+ x = xq.dequeue ();
+ y = yq.dequeue ();
+ d = dq.dequeue ();
+
+ if (x<0 || x>MAX_X || y<0 || y>MAX_Y || dist[y][x]) continue;
+ dist[y][x] = d;
+
+ xq.enqueue (x);
+ xq.enqueue (x);
+ xq.enqueue (x-1);
+ xq.enqueue (x+1);
+
+ yq.enqueue (y-1);
+ yq.enqueue (y+1);
+ yq.enqueue (y);
+ yq.enqueue (y);
+
+ dq.enqueue (d+1);
+ dq.enqueue (d+1);
+ dq.enqueue (d+1);
+ dq.enqueue (d+1);
+ }
+}
+
+Move *
+PathFinder::search (Map *_map, int _x, int _y) {
+ int xpos=_map->xpos ();
+ int ypos=_map->ypos ();
+ if (xpos == _x && ypos == _y) return 0;
+
+ for (int y=0; y<=MAX_Y; y++) {
+ for (int x=0; x<=MAX_X; x++) {
+ if (_map->empty (x, y)) dist[y][x] = 0;
+ else dist[y][x] = PATH_WALL;
+ }
+ }
+
+ BFS (_x, _y);
+
+#if 0
+ for (int y=0; y<=MAX_Y; y++) {
+ for (int x=0; x<=MAX_X; x++) {
+ //if (x==_x && y==_y) {printf ("++ "); continue;}
+ //if (x==xpos && y==ypos) {printf ("@@ "); continue;}
+ if (dist[y][x] == PATH_WALL) {printf ("## "); continue;}
+ printf ("%02d ", dist[y][x]);
+ }
+ printf ("\n");
+ }
+#endif
+
+ int d;
+ Move *move=new Move (xpos, ypos);
+ int oldX, oldY;
+ for (;;) {
+ oldX = xpos;
+ oldY = ypos;
+
+ if (xpos == _x && ypos == _y) {
+ move->finish ();
+ //printf ("move->finish ()\n");
+ return move;
+ }
+
+ d = dist[ypos][xpos];
+
+ while (ypos-1 >= 0 && dist[ypos-1][xpos] < d) {
+ ypos--;
+ d = dist[ypos][xpos];
+ }
+ if (oldY != ypos) {
+ move->step (xpos, ypos);
+ //printf ("step (%d, %d)\n", xpos, ypos);
+ continue;
+ }
+
+ while (ypos+1 <= MAX_Y && dist[ypos+1][xpos] < d) {
+ ypos++;
+ d = dist[ypos][xpos];
+ }
+ if (oldY != ypos) {
+ move->step (xpos, ypos);
+ //printf ("step (%d, %d)\n", xpos, ypos);
+ continue;
+ }
+
+ while (xpos-1 >= 0 && dist[ypos][xpos-1] < d) {
+ xpos--;
+ d = dist[ypos][xpos];
+ }
+ if (oldX != xpos) {
+ move->step (xpos, ypos);
+ //printf ("step (%d, %d)\n", xpos, ypos);
+ continue;
+ }
+
+ while (xpos+1 <= MAX_X && dist[ypos][xpos+1] < d) {
+ xpos++;
+ d = dist[ypos][xpos];
+ }
+ if (oldX != xpos) {
+ move->step (xpos, ypos);
+ //printf ("step (%d, %d)\n", xpos, ypos);
+ continue;
+ }
+
+ delete move;
+ return 0;
+ }
+}
+
+Move*
+PathFinder::drag(int /* x1 */, int /* y1 */, int /* x2 */, int /* y2 */) {
+ return 0;
+}
+
+bool
+PathFinder::canDrag(int /* x */, int /* y */) const {
+ return false;
+}
+
+bool
+PathFinder::canWalkTo(int /* x */, int /* y */) const {
+ return false;
+}
+
+bool
+PathFinder::canDragTo(int /* x */, int /* y */) const {
+ return false;
+}
+
+void
+PathFinder::updatePossibleMoves() {
+}
+
+void
+PathFinder::updatePossibleDestinations(int /* x */, int /* y */) {
+}
+