Leptonica  1.82.0
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  PROCNAME("pixSearchBinaryMaze");
360 
361  if (ppixd) *ppixd = NULL;
362  if (!pixs)
363  return (PTA *)ERROR_PTR("pixs not defined", procName, NULL);
364  pixGetDimensions(pixs, &w, &h, &d);
365  if (d != 1)
366  return (PTA *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
367  if (xi <= 0 || xi >= w)
368  return (PTA *)ERROR_PTR("xi not valid", procName, NULL);
369  if (yi <= 0 || yi >= h)
370  return (PTA *)ERROR_PTR("yi not valid", procName, NULL);
371  pixGetPixel(pixs, xi, yi, &val);
372  if (val != 0)
373  return (PTA *)ERROR_PTR("(xi,yi) not bg pixel", procName, NULL);
374  pixd = NULL;
375  pta = NULL;
376 
377  /* Find a bg pixel near input point (xf, yf) */
378  localSearchForBackground(pixs, &xf, &yf, 5);
379 
380 #if DEBUG_MAZE
381  lept_stderr("(xi, yi) = (%d, %d), (xf, yf) = (%d, %d)\n",
382  xi, yi, xf, yf);
383 #endif /* DEBUG_MAZE */
384 
385  pixm = pixCreate(w, h, 1); /* initialized to OFF */
386  pixp = pixCreate(w, h, 8); /* direction to parent stored as enum val */
387  lines1 = pixGetLinePtrs(pixs, NULL);
388  linem1 = pixGetLinePtrs(pixm, NULL);
389  linep8 = pixGetLinePtrs(pixp, NULL);
390 
391  lq = lqueueCreate(0);
392 
393  /* Prime the queue with the first pixel; it is OFF */
394  el = mazeelCreate(xi, yi, 0); /* don't need direction here */
395  pixSetPixel(pixm, xi, yi, 1); /* mark visited */
396  lqueueAdd(lq, el);
397 
398  /* Fill up the pix storing directions to parents,
399  * stopping when we hit the point (xf, yf) */
400  found = FALSE;
401  while (lqueueGetCount(lq) > 0) {
402  elp = (MAZEEL *)lqueueRemove(lq);
403  x = elp->x;
404  y = elp->y;
405  if (x == xf && y == yf) {
406  found = TRUE;
407  LEPT_FREE(elp);
408  break;
409  }
410 
411  if (x > 0) { /* check to west */
412  val = GET_DATA_BIT(linem1[y], x - 1);
413  if (val == 0) { /* not yet visited */
414  SET_DATA_BIT(linem1[y], x - 1); /* mark visited */
415  val = GET_DATA_BIT(lines1[y], x - 1);
416  if (val == 0) { /* bg, not a wall */
417  SET_DATA_BYTE(linep8[y], x - 1, DIR_EAST); /* parent E */
418  el = mazeelCreate(x - 1, y, 0);
419  lqueueAdd(lq, el);
420  }
421  }
422  }
423  if (y > 0) { /* check north */
424  val = GET_DATA_BIT(linem1[y - 1], x);
425  if (val == 0) { /* not yet visited */
426  SET_DATA_BIT(linem1[y - 1], x); /* mark visited */
427  val = GET_DATA_BIT(lines1[y - 1], x);
428  if (val == 0) { /* bg, not a wall */
429  SET_DATA_BYTE(linep8[y - 1], x, DIR_SOUTH); /* parent S */
430  el = mazeelCreate(x, y - 1, 0);
431  lqueueAdd(lq, el);
432  }
433  }
434  }
435  if (x < w - 1) { /* check east */
436  val = GET_DATA_BIT(linem1[y], x + 1);
437  if (val == 0) { /* not yet visited */
438  SET_DATA_BIT(linem1[y], x + 1); /* mark visited */
439  val = GET_DATA_BIT(lines1[y], x + 1);
440  if (val == 0) { /* bg, not a wall */
441  SET_DATA_BYTE(linep8[y], x + 1, DIR_WEST); /* parent W */
442  el = mazeelCreate(x + 1, y, 0);
443  lqueueAdd(lq, el);
444  }
445  }
446  }
447  if (y < h - 1) { /* check south */
448  val = GET_DATA_BIT(linem1[y + 1], x);
449  if (val == 0) { /* not yet visited */
450  SET_DATA_BIT(linem1[y + 1], x); /* mark visited */
451  val = GET_DATA_BIT(lines1[y + 1], x);
452  if (val == 0) { /* bg, not a wall */
453  SET_DATA_BYTE(linep8[y + 1], x, DIR_NORTH); /* parent N */
454  el = mazeelCreate(x, y + 1, 0);
455  lqueueAdd(lq, el);
456  }
457  }
458  }
459  LEPT_FREE(elp);
460  }
461 
462  lqueueDestroy(&lq, TRUE);
463  pixDestroy(&pixm);
464  LEPT_FREE(linem1);
465 
466  if (ppixd) {
467  pixd = pixUnpackBinary(pixs, 32, 1);
468  *ppixd = pixd;
469  }
470  composeRGBPixel(255, 0, 0, &rpixel); /* start point */
471  composeRGBPixel(0, 255, 0, &gpixel);
472  composeRGBPixel(0, 0, 255, &bpixel); /* end point */
473 
474  if (found) {
475  L_INFO(" Path found\n", procName);
476  pta = ptaCreate(0);
477  x = xf;
478  y = yf;
479  while (1) {
480  ptaAddPt(pta, x, y);
481  if (x == xi && y == yi)
482  break;
483  if (pixd) /* write 'gpixel' onto the path */
484  pixSetPixel(pixd, x, y, gpixel);
485  pixGetPixel(pixp, x, y, &val);
486  if (val == DIR_NORTH)
487  y--;
488  else if (val == DIR_SOUTH)
489  y++;
490  else if (val == DIR_EAST)
491  x++;
492  else if (val == DIR_WEST)
493  x--;
494  }
495  } else {
496  L_INFO(" No path found\n", procName);
497  if (pixd) { /* paint all visited locations */
498  lined32 = pixGetLinePtrs(pixd, NULL);
499  for (i = 0; i < h; i++) {
500  for (j = 0; j < w; j++) {
501  if (GET_DATA_BYTE(linep8[i], j) != 0)
502  SET_DATA_FOUR_BYTES(lined32[i], j, gpixel);
503  }
504  }
505  LEPT_FREE(lined32);
506  }
507  }
508  if (pixd) {
509  pixSetPixel(pixd, xi, yi, rpixel);
510  pixSetPixel(pixd, xf, yf, bpixel);
511  }
512 
513  pixDestroy(&pixp);
514  LEPT_FREE(lines1);
515  LEPT_FREE(linep8);
516  return pta;
517 }
518 
519 
528 static l_int32
530  l_int32 *px,
531  l_int32 *py,
532  l_int32 maxrad)
533 {
534 l_int32 x, y, w, h, r, i, j;
535 l_uint32 val;
536 
537  x = *px;
538  y = *py;
539  pixGetPixel(pix, x, y, &val);
540  if (val == 0) return 0;
541 
542  /* For each value of r, restrict the search to the boundary
543  * pixels in a square centered on (x,y), clipping to the
544  * image boundaries if necessary. */
545  pixGetDimensions(pix, &w, &h, NULL);
546  for (r = 1; r < maxrad; r++) {
547  for (i = -r; i <= r; i++) {
548  if (y + i < 0 || y + i >= h)
549  continue;
550  for (j = -r; j <= r; j++) {
551  if (x + j < 0 || x + j >= w)
552  continue;
553  if (L_ABS(i) != r && L_ABS(j) != r) /* not on "r ring" */
554  continue;
555  pixGetPixel(pix, x + j, y + i, &val);
556  if (val == 0) {
557  *px = x + j;
558  *py = y + i;
559  return 0;
560  }
561  }
562  }
563  }
564  return 1;
565 }
566 
567 
568 
569 /*---------------------------------------------------------------------*
570  * Gray maze search *
571  *---------------------------------------------------------------------*/
726 PTA *
728  l_int32 xi,
729  l_int32 yi,
730  l_int32 xf,
731  l_int32 yf,
732  PIX **ppixd)
733 {
734 l_int32 x, y, w, h, d;
735 l_uint32 val, valr, vals, rpixel, gpixel, bpixel;
736 void **lines8, **liner32, **linep8;
737 l_int32 cost, dist, distparent, sival, sivals;
738 MAZEEL *el, *elp;
739 PIX *pixd; /* optionally plot the path on this RGB version of pixs */
740 PIX *pixr; /* for bookkeeping, to indicate the minimum distance */
741  /* to pixels already visited */
742 PIX *pixp; /* for bookkeeping, to indicate direction to parent */
743 L_HEAP *lh;
744 PTA *pta;
745 
746  PROCNAME("pixSearchGrayMaze");
747 
748  if (ppixd) *ppixd = NULL;
749  if (!pixs)
750  return (PTA *)ERROR_PTR("pixs not defined", procName, NULL);
751  pixGetDimensions(pixs, &w, &h, &d);
752  if (w < 50 || h < 50)
753  return (PTA *)ERROR_PTR("too small: w and h not >= 50", procName, NULL);
754  if (d != 8)
755  return (PTA *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
756  if (xi <= 0 || xi >= w)
757  return (PTA *)ERROR_PTR("xi not valid", procName, NULL);
758  if (yi <= 0 || yi >= h)
759  return (PTA *)ERROR_PTR("yi not valid", procName, NULL);
760  pixd = NULL;
761  pta = NULL;
762 
763  /* Allocate stuff */
764  pixr = pixCreate(w, h, 32);
765  pixSetAll(pixr); /* initialize to max value */
766  pixp = pixCreate(w, h, 8); /* direction to parent stored as enum val */
767  lines8 = pixGetLinePtrs(pixs, NULL);
768  linep8 = pixGetLinePtrs(pixp, NULL);
769  liner32 = pixGetLinePtrs(pixr, NULL);
770  lh = lheapCreate(0, L_SORT_INCREASING); /* always remove closest pixels */
771 
772  /* Prime the heap with the first pixel */
773  pixGetPixel(pixs, xi, yi, &val);
774  el = mazeelCreate(xi, yi, 0); /* don't need direction here */
775  el->distance = 0;
776  pixGetPixel(pixs, xi, yi, &val);
777  el->val = val;
778  pixSetPixel(pixr, xi, yi, 0); /* distance is 0 */
779  lheapAdd(lh, el);
780 
781  /* Breadth-first search with priority queue (implemented by
782  a heap), labeling direction to parents in pixp and minimum
783  distance to visited pixels in pixr. Stop when we pull
784  the destination point (xf, yf) off the queue. */
785  while (lheapGetCount(lh) > 0) {
786  elp = (MAZEEL *)lheapRemove(lh);
787  if (!elp) {
788  L_ERROR("heap broken!!\n", procName);
789  goto cleanup_stuff;
790  }
791  x = elp->x;
792  y = elp->y;
793  if (x == xf && y == yf) { /* exit condition */
794  LEPT_FREE(elp);
795  break;
796  }
797  distparent = (l_int32)elp->distance;
798  val = elp->val;
799  sival = val;
800 
801  if (x > 0) { /* check to west */
802  vals = GET_DATA_BYTE(lines8[y], x - 1);
803  valr = GET_DATA_FOUR_BYTES(liner32[y], x - 1);
804  sivals = (l_int32)vals;
805  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
806  dist = distparent + cost;
807  if (dist < valr) { /* shortest path so far to this pixel */
808  SET_DATA_FOUR_BYTES(liner32[y], x - 1, dist); /* new dist */
809  SET_DATA_BYTE(linep8[y], x - 1, DIR_EAST); /* parent to E */
810  el = mazeelCreate(x - 1, y, 0);
811  el->val = vals;
812  el->distance = dist;
813  lheapAdd(lh, el);
814  }
815  }
816  if (y > 0) { /* check north */
817  vals = GET_DATA_BYTE(lines8[y - 1], x);
818  valr = GET_DATA_FOUR_BYTES(liner32[y - 1], x);
819  sivals = (l_int32)vals;
820  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
821  dist = distparent + cost;
822  if (dist < valr) { /* shortest path so far to this pixel */
823  SET_DATA_FOUR_BYTES(liner32[y - 1], x, dist); /* new dist */
824  SET_DATA_BYTE(linep8[y - 1], x, DIR_SOUTH); /* parent to S */
825  el = mazeelCreate(x, y - 1, 0);
826  el->val = vals;
827  el->distance = dist;
828  lheapAdd(lh, el);
829  }
830  }
831  if (x < w - 1) { /* check east */
832  vals = GET_DATA_BYTE(lines8[y], x + 1);
833  valr = GET_DATA_FOUR_BYTES(liner32[y], x + 1);
834  sivals = (l_int32)vals;
835  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
836  dist = distparent + cost;
837  if (dist < valr) { /* shortest path so far to this pixel */
838  SET_DATA_FOUR_BYTES(liner32[y], x + 1, dist); /* new dist */
839  SET_DATA_BYTE(linep8[y], x + 1, DIR_WEST); /* parent to W */
840  el = mazeelCreate(x + 1, y, 0);
841  el->val = vals;
842  el->distance = dist;
843  lheapAdd(lh, el);
844  }
845  }
846  if (y < h - 1) { /* check south */
847  vals = GET_DATA_BYTE(lines8[y + 1], x);
848  valr = GET_DATA_FOUR_BYTES(liner32[y + 1], x);
849  sivals = (l_int32)vals;
850  cost = 1 + L_ABS(sivals - sival); /* cost to move to this pixel */
851  dist = distparent + cost;
852  if (dist < valr) { /* shortest path so far to this pixel */
853  SET_DATA_FOUR_BYTES(liner32[y + 1], x, dist); /* new dist */
854  SET_DATA_BYTE(linep8[y + 1], x, DIR_NORTH); /* parent to N */
855  el = mazeelCreate(x, y + 1, 0);
856  el->val = vals;
857  el->distance = dist;
858  lheapAdd(lh, el);
859  }
860  }
861  LEPT_FREE(elp);
862  }
863 
864  lheapDestroy(&lh, TRUE);
865 
866  if (ppixd) {
867  pixd = pixConvert8To32(pixs);
868  *ppixd = pixd;
869  }
870  composeRGBPixel(255, 0, 0, &rpixel); /* start point */
871  composeRGBPixel(0, 255, 0, &gpixel);
872  composeRGBPixel(0, 0, 255, &bpixel); /* end point */
873 
874  x = xf;
875  y = yf;
876  pta = ptaCreate(0);
877  while (1) { /* write path onto pixd */
878  ptaAddPt(pta, x, y);
879  if (x == xi && y == yi)
880  break;
881  if (pixd)
882  pixSetPixel(pixd, x, y, gpixel);
883  pixGetPixel(pixp, x, y, &val);
884  if (val == DIR_NORTH)
885  y--;
886  else if (val == DIR_SOUTH)
887  y++;
888  else if (val == DIR_EAST)
889  x++;
890  else if (val == DIR_WEST)
891  x--;
892  pixGetPixel(pixr, x, y, &val);
893 
894 #if DEBUG_PATH
895  lept_stderr("(x,y) = (%d, %d); dist = %d\n", x, y, val);
896 #endif /* DEBUG_PATH */
897 
898  }
899  if (pixd) {
900  pixSetPixel(pixd, xi, yi, rpixel);
901  pixSetPixel(pixd, xf, yf, bpixel);
902  }
903 
904 cleanup_stuff:
905  lheapDestroy(&lh, TRUE);
906  pixDestroy(&pixp);
907  pixDestroy(&pixr);
908  LEPT_FREE(lines8);
909  LEPT_FREE(linep8);
910  LEPT_FREE(liner32);
911  return pta;
912 }
#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:154
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:283
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
static l_int32 localSearchForBackground(PIX *pix, l_int32 *px, l_int32 *py, l_int32 maxrad)
localSearchForBackground()
Definition: maze.c:529
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:727
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:621
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
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:1949
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:190
l_ok pixSetAll(PIX *pix)
pixSetAll()
Definition: pix2.c:817
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
Definition: pix2.c:2751
@ L_SORT_INCREASING
Definition: pix.h:729
PIX * pixUnpackBinary(PIX *pixs, l_int32 depth, l_int32 invert)
pixUnpackBinary()
Definition: pixconv.c:1913
PIX * pixConvert8To32(PIX *pixs)
pixConvert8To32()
Definition: pixconv.c:3422
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:343
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:286
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:134
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:257
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:188
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
Definition: heap.h:78
Definition: queue.h:65
Definition: pix.h:139
Definition: pix.h:517
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306