56 #include <config_auto.h> 64 #include "allheaders.h" 66 static const l_int32 MinMazeWidth = 50;
67 static const l_int32 MinMazeHeight = 50;
69 static const l_float32 DefaultWallProbability = 0.65;
70 static const l_float32 DefaultAnisotropyRatio = 0.25;
90 static MAZEEL *mazeelCreate(l_int32 x, l_int32 y, l_int32 dir);
92 l_int32 *py, l_int32 maxrad);
154 l_float32 frand, wallpf, testp;
168 if (w < MinMazeWidth)
170 if (h < MinMazeHeight)
172 if (xi <= 0 || xi >= w)
174 if (yi <= 0 || yi >= h)
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;
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",
195 el = mazeelCreate(xi, yi, START_LOC);
209 frand = (l_float32)rand() / (l_float32)RAND_MAX;
213 if (frand <= testp) {
216 el = mazeelCreate(x - 1, y, DIR_WEST);
225 frand = (l_float32)rand() / (l_float32)RAND_MAX;
227 if (dir == DIR_NORTH)
229 if (frand <= testp) {
232 el = mazeelCreate(x, y - 1, DIR_NORTH);
241 frand = (l_float32)rand() / (l_float32)RAND_MAX;
245 if (frand <= testp) {
248 el = mazeelCreate(x + 1, y, DIR_EAST);
257 frand = (l_float32)rand() / (l_float32)RAND_MAX;
259 if (dir == DIR_SOUTH)
261 if (frand <= testp) {
264 el = mazeelCreate(x, y + 1, DIR_SOUTH);
279 mazeelCreate(l_int32 x,
349 l_int32 i, j, x, y, w, h, d, found;
350 l_uint32 val, rpixel, gpixel, bpixel;
351 void **lines1, **linem1, **linep8, **lined32;
359 PROCNAME(
"pixSearchBinaryMaze");
361 if (ppixd) *ppixd = NULL;
363 return (
PTA *)ERROR_PTR(
"pixs not defined", procName, NULL);
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);
373 return (
PTA *)ERROR_PTR(
"(xi,yi) not bg pixel", procName, NULL);
381 lept_stderr(
"(xi, yi) = (%d, %d), (xf, yf) = (%d, %d)\n",
394 el = mazeelCreate(xi, yi, 0);
405 if (x == xf && y == yf) {
418 el = mazeelCreate(x - 1, y, 0);
430 el = mazeelCreate(x, y - 1, 0);
442 el = mazeelCreate(x + 1, y, 0);
454 el = mazeelCreate(x, y + 1, 0);
475 L_INFO(
" Path found\n", procName);
481 if (x == xi && y == yi)
486 if (val == DIR_NORTH)
488 else if (val == DIR_SOUTH)
490 else if (val == DIR_EAST)
492 else if (val == DIR_WEST)
496 L_INFO(
" No path found\n", procName);
499 for (i = 0; i < h; i++) {
500 for (j = 0; j < w; j++) {
534 l_int32 x, y, w, h, r, i, j;
540 if (val == 0)
return 0;
546 for (r = 1; r < maxrad; r++) {
547 for (i = -r; i <= r; i++) {
548 if (y + i < 0 || y + i >= h)
550 for (j = -r; j <= r; j++) {
551 if (x + j < 0 || x + j >= w)
553 if (L_ABS(i) != r && L_ABS(j) != r)
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;
746 PROCNAME(
"pixSearchGrayMaze");
748 if (ppixd) *ppixd = NULL;
750 return (
PTA *)ERROR_PTR(
"pixs not defined", procName, NULL);
752 if (w < 50 || h < 50)
753 return (
PTA *)ERROR_PTR(
"too small: w and h not >= 50", procName, NULL);
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);
774 el = mazeelCreate(xi, yi, 0);
788 L_ERROR(
"heap broken!!\n", procName);
793 if (x == xf && y == yf) {
797 distparent = (l_int32)elp->distance;
804 sivals = (l_int32)vals;
805 cost = 1 + L_ABS(sivals - sival);
806 dist = distparent + cost;
810 el = mazeelCreate(x - 1, y, 0);
819 sivals = (l_int32)vals;
820 cost = 1 + L_ABS(sivals - sival);
821 dist = distparent + cost;
825 el = mazeelCreate(x, y - 1, 0);
834 sivals = (l_int32)vals;
835 cost = 1 + L_ABS(sivals - sival);
836 dist = distparent + cost;
840 el = mazeelCreate(x + 1, y, 0);
849 sivals = (l_int32)vals;
850 cost = 1 + L_ABS(sivals - sival);
851 dist = distparent + cost;
855 el = mazeelCreate(x, y + 1, 0);
879 if (x == xi && y == yi)
884 if (val == DIR_NORTH)
886 else if (val == DIR_SOUTH)
888 else if (val == DIR_EAST)
890 else if (val == DIR_WEST)
895 lept_stderr(
"(x,y) = (%d, %d); dist = %d\n", x, y, val);
PIX * pixUnpackBinary(PIX *pixs, l_int32 depth, l_int32 invert)
pixUnpackBinary()
PTA * pixSearchGrayMaze(PIX *pixs, l_int32 xi, l_int32 yi, l_int32 xf, l_int32 yf, PIX **ppixd)
pixSearchGrayMaze()
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
PTA * ptaCreate(l_int32 n)
ptaCreate()
PIX * pixConvert8To32(PIX *pixs)
pixConvert8To32()
void ** pixGetLinePtrs(PIX *pix, l_int32 *psize)
pixGetLinePtrs()
void lept_stderr(const char *fmt,...)
lept_stderr()
#define GET_DATA_FOUR_BYTES(pdata, n)
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
l_ok pixSetAll(PIX *pix)
pixSetAll()
static l_int32 localSearchForBackground(PIX *pix, l_int32 *px, l_int32 *py, l_int32 maxrad)
localSearchForBackground()
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
#define GET_DATA_BIT(pdata, n)
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
#define SET_DATA_BYTE(pdata, n, val)
#define GET_DATA_BYTE(pdata, n)
void * lheapRemove(L_HEAP *lh)
lheapRemove()
void pixDestroy(PIX **ppix)
pixDestroy()
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
PIX * generateBinaryMaze(l_int32 w, l_int32 h, l_int32 xi, l_int32 yi, l_float32 wallps, l_float32 ranis)
generateBinaryMaze()
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
#define SET_DATA_FOUR_BYTES(pdata, n, val)
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
PTA * pixSearchBinaryMaze(PIX *pixs, l_int32 xi, l_int32 yi, l_int32 xf, l_int32 yf, PIX **ppixd)
pixSearchBinaryMaze()
l_ok composeRGBPixel(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *ppixel)
composeRGBPixel()
#define SET_DATA_BIT(pdata, n)