Leptonica  1.83.1
Image processing and image analysis suite
maze.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
27 
55 #ifdef HAVE_CONFIG_H
56 #include <config_auto.h>
57 #endif /* HAVE_CONFIG_H */
58 
59 #include <string.h>
60 #ifdef _WIN32
61 #include <stdlib.h>
62 #include <time.h>
63 #endif /* _WIN32 */
64 #include "allheaders.h"
65 
66 static const l_int32 MinMazeWidth = 50;
67 static const l_int32 MinMazeHeight = 50;
68 
69 static const l_float32 DefaultWallProbability = 0.65;
70 static const l_float32 DefaultAnisotropyRatio = 0.25;
71 
72 enum { /* direction from parent to newly created element */
73  START_LOC = 0,
74  DIR_NORTH = 1,
75  DIR_SOUTH = 2,
76  DIR_WEST = 3,
77  DIR_EAST = 4
78 };
79 
80 struct MazeElement {
81  l_float32 distance;
82  l_int32 x;
83  l_int32 y;
84  l_uint32 val; /* value of maze pixel at this location */
85  l_int32 dir; /* direction from parent to child */
86 };
87 typedef struct MazeElement MAZEEL;
88 
89 
90 static MAZEEL *mazeelCreate(l_int32 x, l_int32 y, l_int32 dir);
91 static l_int32 localSearchForBackground(PIX *pix, l_int32 *px,
92  l_int32 *py, l_int32 maxrad);
93 
94 #ifndef NO_CONSOLE_IO
95 #define DEBUG_PATH 0
96 #define DEBUG_MAZE 0
97 #endif /* ~NO_CONSOLE_IO */
98 
99 /*---------------------------------------------------------------------*
100  * Binary maze generation as cellular automaton *
101  *---------------------------------------------------------------------*/
144 PIX *
146  l_int32 h,
147  l_int32 xi,
148  l_int32 yi,
149  l_float32 wallps,
150  l_float32 ranis)
151 {
152 l_int32 x, y, dir;
153 l_uint32 val;
154 l_float32 frand, wallpf, testp;
155 MAZEEL *el, *elp;
156 PIX *pixd; /* the destination maze */
157 PIX *pixm; /* for bookkeeping, to indicate pixels already visited */
158 L_QUEUE *lq;
159 
160  /* On Windows, seeding is apparently necessary to get decent mazes.
161  * Windows rand() returns a value up to 2^15 - 1, whereas unix
162  * rand() returns a value up to 2^31 - 1. Therefore the generated
163  * mazes will differ on the two platforms. */
164 #ifdef _WIN32
165  srand(28*333);
166 #endif /* _WIN32 */
167 
168  if (w < MinMazeWidth)
169  w = MinMazeWidth;
170  if (h < MinMazeHeight)
171  h = MinMazeHeight;
172  if (xi <= 0 || xi >= w)
173  xi = w / 6;
174  if (yi <= 0 || yi >= h)
175  yi = h / 5;
176  if (wallps < 0.05 || wallps > 0.95)
177  wallps = DefaultWallProbability;
178  if (ranis < 0.05 || ranis > 1.0)
179  ranis = DefaultAnisotropyRatio;
180  wallpf = wallps * ranis;
181 
182 #if DEBUG_MAZE
183  lept_stderr("(w, h) = (%d, %d), (xi, yi) = (%d, %d)\n", w, h, xi, yi);
184  lept_stderr("Using: prob(wall) = %7.4f, anisotropy factor = %7.4f\n",
185  wallps, ranis);
186 #endif /* DEBUG_MAZE */
187 
188  /* These are initialized to OFF */
189  pixd = pixCreate(w, h, 1);
190  pixm = pixCreate(w, h, 1);
191 
192  lq = lqueueCreate(0);
193 
194  /* Prime the queue with the first pixel; it is OFF */
195  el = mazeelCreate(xi, yi, START_LOC);
196  pixSetPixel(pixm, xi, yi, 1); /* mark visited */
197  lqueueAdd(lq, el);
198 
199  /* While we're at it ... */
200  while (lqueueGetCount(lq) > 0) {
201  elp = (MAZEEL *)lqueueRemove(lq);
202  x = elp->x;
203  y = elp->y;
204  dir = elp->dir;
205  if (x > 0) { /* check west */
206  pixGetPixel(pixm, x - 1, y, &val);
207  if (val == 0) { /* not yet visited */
208  pixSetPixel(pixm, x - 1, y, 1); /* mark visited */
209  frand = (l_float32)rand() / (l_float32)RAND_MAX;
210  testp = wallps;
211  if (dir == DIR_WEST)
212  testp = wallpf;
213  if (frand <= testp) { /* make it a wall */
214  pixSetPixel(pixd, x - 1, y, 1);
215  } else { /* not a wall */
216  el = mazeelCreate(x - 1, y, DIR_WEST);
217  lqueueAdd(lq, el);
218  }
219  }
220  }
221  if (y > 0) { /* check north */
222  pixGetPixel(pixm, x, y - 1, &val);
223  if (val == 0) { /* not yet visited */
224  pixSetPixel(pixm, x, y - 1, 1); /* mark visited */
225  frand = (l_float32)rand() / (l_float32)RAND_MAX;
226  testp = wallps;
227  if (dir == DIR_NORTH)
228  testp = wallpf;
229  if (frand <= testp) { /* make it a wall */
230  pixSetPixel(pixd, x, y - 1, 1);
231  } else { /* not a wall */
232  el = mazeelCreate(x, y - 1, DIR_NORTH);
233  lqueueAdd(lq, el);
234  }
235  }
236  }
237  if (x < w - 1) { /* check east */
238  pixGetPixel(pixm, x + 1, y, &val);
239  if (val == 0) { /* not yet visited */
240  pixSetPixel(pixm, x + 1, y, 1); /* mark visited */
241  frand = (l_float32)rand() / (l_float32)RAND_MAX;
242  testp = wallps;
243  if (dir == DIR_EAST)
244  testp = wallpf;
245  if (frand <= testp) { /* make it a wall */
246  pixSetPixel(pixd, x + 1, y, 1);
247  } else { /* not a wall */
248  el = mazeelCreate(x + 1, y, DIR_EAST);
249  lqueueAdd(lq, el);
250  }
251  }
252  }
253  if (y < h - 1) { /* check south */
254  pixGetPixel(pixm, x, y + 1, &val);
255  if (val == 0) { /* not yet visited */
256  pixSetPixel(pixm, x, y + 1, 1); /* mark visited */
257  frand = (l_float32)rand() / (l_float32)RAND_MAX;
258  testp = wallps;
259  if (dir == DIR_SOUTH)
260  testp = wallpf;
261  if (frand <= testp) { /* make it a wall */
262  pixSetPixel(pixd, x, y + 1, 1);
263  } else { /* not a wall */
264  el = mazeelCreate(x, y + 1, DIR_SOUTH);
265  lqueueAdd(lq, el);
266  }
267  }
268  }
269  LEPT_FREE(elp);
270  }
271 
272  lqueueDestroy(&lq, TRUE);
273  pixDestroy(&pixm);
274  return pixd;
275 }
276 
277 
278 static MAZEEL *
279 mazeelCreate(l_int32 x,
280  l_int32 y,
281  l_int32 dir)
282 {
283 MAZEEL *el;
284 
285  el = (MAZEEL *)LEPT_CALLOC(1, sizeof(MAZEEL));
286  el->x = x;
287  el->y = y;
288  el->dir = dir;
289  return el;
290 }
291 
292 
293 /*---------------------------------------------------------------------*
294  * Binary maze search *
295  *---------------------------------------------------------------------*/
341 PTA *
343  l_int32 xi,
344  l_int32 yi,
345  l_int32 xf,
346  l_int32 yf,
347  PIX **ppixd)
348 {
349 l_int32 i, j, x, y, w, h, d, found;
350 l_uint32 val, rpixel, gpixel, bpixel;
351 void **lines1, **linem1, **linep8, **lined32;
352 MAZEEL *el, *elp;
353 PIX *pixd; /* the shortest path written on the maze image */
354 PIX *pixm; /* for bookkeeping, to indicate pixels already visited */
355 PIX *pixp; /* for bookkeeping, to indicate direction to parent */
356 L_QUEUE *lq;
357 PTA *pta;
358 
359  if (ppixd) *ppixd = NULL;
360  if (!pixs)
361  return (PTA *)ERROR_PTR("pixs not defined", __func__, NULL);
362  pixGetDimensions(pixs, &w, &h, &d);
363  if (d != 1)
364  return (PTA *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
365  if (xi <= 0 || xi >= w)
366  return (PTA *)ERROR_PTR("xi not valid", __func__, NULL);
367  if (yi <= 0 || yi >= h)
368  return (PTA *)ERROR_PTR("yi not valid", __func__, NULL);
369  pixGetPixel(pixs, xi, yi, &val);
370  if (val != 0)
371  return (PTA *)ERROR_PTR("(xi,yi) not bg pixel", __func__, NULL);
372  pixd = NULL;
373  pta = NULL;
374 
375  /* Find a bg pixel near input point (xf, yf) */
376  localSearchForBackground(pixs, &xf, &yf, 5);
377 
378 #if DEBUG_MAZE
379  lept_stderr("(xi, yi) = (%d, %d), (xf, yf) = (%d, %d)\n",
380  xi, yi, xf, yf);
381 #endif /* DEBUG_MAZE */
382 
383  pixm = pixCreate(w, h, 1); /* initialized to OFF */
384  pixp = pixCreate(w, h, 8); /* direction to parent stored as enum val */
385  lines1 = pixGetLinePtrs(pixs, NULL);
386  linem1 = pixGetLinePtrs(pixm, NULL);
387  linep8 = pixGetLinePtrs(pixp, NULL);
388 
389  lq = lqueueCreate(0);
390 
391  /* Prime the queue with the first pixel; it is OFF */
392  el = mazeelCreate(xi, yi, 0); /* don't need direction here */
393  pixSetPixel(pixm, xi, yi, 1); /* mark visited */
394  lqueueAdd(lq, el);
395 
396  /* Fill up the pix storing directions to parents,
397  * stopping when we hit the point (xf, yf) */
398  found = FALSE;
399  while (lqueueGetCount(lq) > 0) {
400  elp = (MAZEEL *)lqueueRemove(lq);
401  x = elp->x;
402  y = elp->y;
403  if (x == xf && y == yf) {
404  found = TRUE;
405  LEPT_FREE(elp);
406  break;
407  }
408 
409  if (x > 0) { /* check to west */
410  val = GET_DATA_BIT(linem1[y], x - 1);
411  if (val == 0) { /* not yet visited */
412  SET_DATA_BIT(linem1[y], x - 1); /* mark visited */
413  val = GET_DATA_BIT(lines1[y], x - 1);
414  if (val == 0) { /* bg, not a wall */
415  SET_DATA_BYTE(linep8[y], x - 1, DIR_EAST); /* parent E */
416  el = mazeelCreate(x - 1, y, 0);
417  lqueueAdd(lq, el);
418  }
419  }
420  }
421  if (y > 0) { /* check north */
422  val = GET_DATA_BIT(linem1[y - 1], x);
423  if (val == 0) { /* not yet visited */
424  SET_DATA_BIT(linem1[y - 1], x); /* mark visited */
425  val = GET_DATA_BIT(lines1[y - 1], x);
426  if (val == 0) { /* bg, not a wall */
427  SET_DATA_BYTE(linep8[y - 1], x, DIR_SOUTH); /* parent S */
428  el = mazeelCreate(x, y - 1, 0);
429  lqueueAdd(lq, el);
430  }
431  }
432  }
433  if (x < w - 1) { /* check east */
434  val = GET_DATA_BIT(linem1[y], x + 1);
435  if (val == 0) { /* not yet visited */
436  SET_DATA_BIT(linem1[y], x + 1); /* mark visited */
437  val = GET_DATA_BIT(lines1[y], x + 1);
438  if (val == 0) { /* bg, not a wall */
439  SET_DATA_BYTE(linep8[y], x + 1, DIR_WEST); /* parent W */
440  el = mazeelCreate(x + 1, y, 0);
441  lqueueAdd(lq, el);
442  }
443  }
444  }
445  if (y < h - 1) { /* check south */
446  val = GET_DATA_BIT(linem1[y + 1], x);
447  if (val == 0) { /* not yet visited */
448  SET_DATA_BIT(linem1[y + 1], x); /* mark visited */
449  val = GET_DATA_BIT(lines1[y + 1], x);
450  if (val == 0) { /* bg, not a wall */
451  SET_DATA_BYTE(linep8[y + 1], x, DIR_NORTH); /* parent N */
452  el = mazeelCreate(x, y + 1, 0);
453  lqueueAdd(lq, el);
454  }
455  }
456  }
457  LEPT_FREE(elp);
458  }
459 
460  lqueueDestroy(&lq, TRUE);
461  pixDestroy(&pixm);
462  LEPT_FREE(linem1);
463 
464  if (ppixd) {
465  pixd = pixUnpackBinary(pixs, 32, 1);
466  *ppixd = pixd;
467  }
468  composeRGBPixel(255, 0, 0, &rpixel); /* start point */
469  composeRGBPixel(0, 255, 0, &gpixel);
470  composeRGBPixel(0, 0, 255, &bpixel); /* end point */
471 
472  if (found) {
473  L_INFO(" Path found\n", __func__);
474  pta = ptaCreate(0);
475  x = xf;
476  y = yf;
477  while (1) {
478  ptaAddPt(pta, x, y);
479  if (x == xi && y == yi)
480  break;
481  if (pixd) /* write 'gpixel' onto the path */
482  pixSetPixel(pixd, x, y, gpixel);
483  pixGetPixel(pixp, x, y, &val);
484  if (val == DIR_NORTH)
485  y--;
486  else if (val == DIR_SOUTH)
487  y++;
488  else if (val == DIR_EAST)
489  x++;
490  else if (val == DIR_WEST)
491  x--;
492  }
493  } else {
494  L_INFO(" No path found\n", __func__);
495  if (pixd) { /* paint all visited locations */
496  lined32 = pixGetLinePtrs(pixd, NULL);
497  for (i = 0; i < h; i++) {
498  for (j = 0; j < w; j++) {
499  if (GET_DATA_BYTE(linep8[i], j) != 0)
500  SET_DATA_FOUR_BYTES(lined32[i], j, gpixel);
501  }
502  }
503  LEPT_FREE(lined32);
504  }
505  }
506  if (pixd) {
507  pixSetPixel(pixd, xi, yi, rpixel);
508  pixSetPixel(pixd, xf, yf, bpixel);
509  }
510 
511  pixDestroy(&pixp);
512  LEPT_FREE(lines1);
513  LEPT_FREE(linep8);
514  return pta;
515 }
516 
517 
526 static l_int32
528  l_int32 *px,
529  l_int32 *py,
530  l_int32 maxrad)
531 {
532 l_int32 x, y, w, h, r, i, j;
533 l_uint32 val;
534 
535  x = *px;
536  y = *py;
537  pixGetPixel(pix, x, y, &val);
538  if (val == 0) return 0;
539 
540  /* For each value of r, restrict the search to the boundary
541  * pixels in a square centered on (x,y), clipping to the
542  * image boundaries if necessary. */
543  pixGetDimensions(pix, &w, &h, NULL);
544  for (r = 1; r < maxrad; r++) {
545  for (i = -r; i <= r; i++) {
546  if (y + i < 0 || y + i >= h)
547  continue;
548  for (j = -r; j <= r; j++) {
549  if (x + j < 0 || x + j >= w)
550  continue;
551  if (L_ABS(i) != r && L_ABS(j) != r) /* not on "r ring" */
552  continue;
553  pixGetPixel(pix, x + j, y + i, &val);
554  if (val == 0) {
555  *px = x + j;
556  *py = y + i;
557  return 0;
558  }
559  }
560  }
561  }
562  return 1;
563 }
564 
565 
566 
567 /*---------------------------------------------------------------------*
568  * Gray maze search *
569  *---------------------------------------------------------------------*/
724 PTA *
726  l_int32 xi,
727  l_int32 yi,
728  l_int32 xf,
729  l_int32 yf,
730  PIX **ppixd)
731 {
732 l_int32 x, y, w, h, d;
733 l_uint32 val, valr, vals, rpixel, gpixel, bpixel;
734 void **lines8, **liner32, **linep8;
735 l_int32 cost, dist, distparent, sival, sivals;
736 MAZEEL *el, *elp;
737 PIX *pixd; /* optionally plot the path on this RGB version of pixs */
738 PIX *pixr; /* for bookkeeping, to indicate the minimum distance */
739  /* to pixels already visited */
740 PIX *pixp; /* for bookkeeping, to indicate direction to parent */
741 L_HEAP *lh;
742 PTA *pta;
743 
744  if (ppixd) *ppixd = NULL;
745  if (!pixs)
746  return (PTA *)ERROR_PTR("pixs not defined", __func__, NULL);
747  pixGetDimensions(pixs, &w, &h, &d);
748  if (w < 50 || h < 50)
749  return (PTA *)ERROR_PTR("too small: w and h not >= 50", __func__, NULL);
750  if (d != 8)
751  return (PTA *)ERROR_PTR("pixs not 8 bpp", __func__, NULL);
752  if (xi <= 0 || xi >= w)
753  return (PTA *)ERROR_PTR("xi not valid", __func__, NULL);
754  if (yi <= 0 || yi >= h)
755  return (PTA *)ERROR_PTR("yi not valid", __func__, NULL);
756  pixd = NULL;
757  pta = NULL;
758 
759  /* Allocate stuff */
760  pixr = pixCreate(w, h, 32);
761  pixSetAll(pixr); /* initialize to max value */
762  pixp = pixCreate(w, h, 8); /* direction to parent stored as enum val */
763  lines8 = pixGetLinePtrs(pixs, NULL);
764  linep8 = pixGetLinePtrs(pixp, NULL);
765  liner32 = pixGetLinePtrs(pixr, NULL);
766  lh = lheapCreate(0, L_SORT_INCREASING); /* always remove closest pixels */
767 
768  /* Prime the heap with the first pixel */
769  pixGetPixel(pixs, xi, yi, &val);
770  el = mazeelCreate(xi, yi, 0); /* don't need direction here */
771  el->distance = 0;
772  pixGetPixel(pixs, xi, yi, &val);
773  el->val = val;
774  pixSetPixel(pixr, xi, yi, 0); /* distance is 0 */
775  lheapAdd(lh, el);
776 
777  /* Breadth-first search with priority queue (implemented by
778  a heap), labeling direction to parents in pixp and minimum
779  distance to visited pixels in pixr. Stop when we pull
780  the destination point (xf, yf) off the queue. */
781  while (lheapGetCount(lh) > 0) {
782  elp = (MAZEEL *)lheapRemove(lh);
783  if (!elp) {
784  L_ERROR("heap broken!!\n", __func__);
785  goto cleanup_stuff;
786  }
787  x = elp->x;
788  y = elp->y;
789  if (x == xf && y == yf) { /* exit condition */
790  LEPT_FREE(elp);
791  break;
792  }
793  distparent = (l_int32)elp->distance;
794  val = elp->val;
795  sival = val;
796 
797  if (x > 0) { /* check to west */
798  vals = GET_DATA_BYTE(lines8[y], x - 1);
799  valr = GET_DATA_FOUR_BYTES(liner32[y], x - 1);
800  sivals = (l_int32)vals;
801  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
802  dist = distparent + cost;
803  if (dist < valr) { /* shortest path so far to this pixel */
804  SET_DATA_FOUR_BYTES(liner32[y], x - 1, dist); /* new dist */
805  SET_DATA_BYTE(linep8[y], x - 1, DIR_EAST); /* parent to E */
806  el = mazeelCreate(x - 1, y, 0);
807  el->val = vals;
808  el->distance = dist;
809  lheapAdd(lh, el);
810  }
811  }
812  if (y > 0) { /* check north */
813  vals = GET_DATA_BYTE(lines8[y - 1], x);
814  valr = GET_DATA_FOUR_BYTES(liner32[y - 1], x);
815  sivals = (l_int32)vals;
816  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
817  dist = distparent + cost;
818  if (dist < valr) { /* shortest path so far to this pixel */
819  SET_DATA_FOUR_BYTES(liner32[y - 1], x, dist); /* new dist */
820  SET_DATA_BYTE(linep8[y - 1], x, DIR_SOUTH); /* parent to S */
821  el = mazeelCreate(x, y - 1, 0);
822  el->val = vals;
823  el->distance = dist;
824  lheapAdd(lh, el);
825  }
826  }
827  if (x < w - 1) { /* check east */
828  vals = GET_DATA_BYTE(lines8[y], x + 1);
829  valr = GET_DATA_FOUR_BYTES(liner32[y], x + 1);
830  sivals = (l_int32)vals;
831  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
832  dist = distparent + cost;
833  if (dist < valr) { /* shortest path so far to this pixel */
834  SET_DATA_FOUR_BYTES(liner32[y], x + 1, dist); /* new dist */
835  SET_DATA_BYTE(linep8[y], x + 1, DIR_WEST); /* parent to W */
836  el = mazeelCreate(x + 1, y, 0);
837  el->val = vals;
838  el->distance = dist;
839  lheapAdd(lh, el);
840  }
841  }
842  if (y < h - 1) { /* check south */
843  vals = GET_DATA_BYTE(lines8[y + 1], x);
844  valr = GET_DATA_FOUR_BYTES(liner32[y + 1], x);
845  sivals = (l_int32)vals;
846  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
847  dist = distparent + cost;
848  if (dist < valr) { /* shortest path so far to this pixel */
849  SET_DATA_FOUR_BYTES(liner32[y + 1], x, dist); /* new dist */
850  SET_DATA_BYTE(linep8[y + 1], x, DIR_NORTH); /* parent to N */
851  el = mazeelCreate(x, y + 1, 0);
852  el->val = vals;
853  el->distance = dist;
854  lheapAdd(lh, el);
855  }
856  }
857  LEPT_FREE(elp);
858  }
859 
860  lheapDestroy(&lh, TRUE);
861 
862  if (ppixd) {
863  pixd = pixConvert8To32(pixs);
864  *ppixd = pixd;
865  }
866  composeRGBPixel(255, 0, 0, &rpixel); /* start point */
867  composeRGBPixel(0, 255, 0, &gpixel);
868  composeRGBPixel(0, 0, 255, &bpixel); /* end point */
869 
870  x = xf;
871  y = yf;
872  pta = ptaCreate(0);
873  while (1) { /* write path onto pixd */
874  ptaAddPt(pta, x, y);
875  if (x == xi && y == yi)
876  break;
877  if (pixd)
878  pixSetPixel(pixd, x, y, gpixel);
879  pixGetPixel(pixp, x, y, &val);
880  if (val == DIR_NORTH)
881  y--;
882  else if (val == DIR_SOUTH)
883  y++;
884  else if (val == DIR_EAST)
885  x++;
886  else if (val == DIR_WEST)
887  x--;
888  pixGetPixel(pixr, x, y, &val);
889 
890 #if DEBUG_PATH
891  lept_stderr("(x,y) = (%d, %d); dist = %d\n", x, y, val);
892 #endif /* DEBUG_PATH */
893 
894  }
895  if (pixd) {
896  pixSetPixel(pixd, xi, yi, rpixel);
897  pixSetPixel(pixd, xf, yf, bpixel);
898  }
899 
900 cleanup_stuff:
901  lheapDestroy(&lh, TRUE);
902  pixDestroy(&pixp);
903  pixDestroy(&pixr);
904  LEPT_FREE(lines8);
905  LEPT_FREE(linep8);
906  LEPT_FREE(liner32);
907  return pta;
908 }
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
#define SET_DATA_FOUR_BYTES(pdata, n, val)
Definition: arrayaccess.h:235
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define GET_DATA_FOUR_BYTES(pdata, n)
Definition: arrayaccess.h:231
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:152
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:273
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:189
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:243
static l_int32 localSearchForBackground(PIX *pix, l_int32 *px, l_int32 *py, l_int32 maxrad)
localSearchForBackground()
Definition: maze.c:527
PIX * generateBinaryMaze(l_int32 w, l_int32 h, l_int32 xi, l_int32 yi, l_float32 wallps, l_float32 ranis)
generateBinaryMaze()
Definition: maze.c:145
PTA * pixSearchGrayMaze(PIX *pixs, l_int32 xi, l_int32 yi, l_int32 xf, l_int32 yf, PIX **ppixd)
pixSearchGrayMaze()
Definition: maze.c:725
PTA * pixSearchBinaryMaze(PIX *pixs, l_int32 xi, l_int32 yi, l_int32 xf, l_int32 yf, PIX **ppixd)
pixSearchBinaryMaze()
Definition: maze.c:342
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:608
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1074
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
void ** pixGetLinePtrs(PIX *pix, l_int32 *psize)
pixGetLinePtrs()
Definition: pix1.c:1844
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
Definition: pix2.c:263
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
Definition: pix2.c:192
l_ok pixSetAll(PIX *pix)
pixSetAll()
Definition: pix2.c:799
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
Definition: pix2.c:2728
@ L_SORT_INCREASING
Definition: pix.h:522
PIX * pixUnpackBinary(PIX *pixs, l_int32 depth, l_int32 invert)
pixUnpackBinary()
Definition: pixconv.c:1873
PIX * pixConvert8To32(PIX *pixs)
pixConvert8To32()
Definition: pixconv.c:3332
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:328
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:276
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:132
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:249
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:184
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
Definition: heap.h:78
Definition: queue.h:65
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306