[Rick]

Hello, I tryed to make a Maze Generator Filter Script. I converted a c algorithm into a pawno algorithm. My filterscript is working fine when I wanna generate little mazes (size < 7), but when I want generate big mazes it returns Unknown cmd whereas my function isn't finished to run.

I would appreciate if someone can help me to solve this problem, and maybe it will be awesome if some guys are interest to join the project.

Код:

#include <a_samp>

#define MAX 61  // 30 * 2 + 1
#define CELL 900  // 30 * 30
#define WALL 1
#define PATH 0

new size=6;
new indeks = 0;
new maze[MAX][MAX];
new backtrack_x[CELL];
new backtrack_y[CELL];
new finished=0;


public OnFilterScriptInit()
{
	print("\n--------------------------------------");
	print(" Rick Maze Filterscript");
	print("--------------------------------------\n");
	return 1;
}

public OnFilterScriptExit()
{
	return 1;
}


init_maze(maze[MAX][MAX])
{
     for(new a = 0; a < MAX; a++)
     {
         for(new b = 0; b < MAX; b++)
         {
             if(a % 2 == 0 || b % 2 == 0)
                 maze[a][b] = 1;
             else
                 maze[a][b] = PATH;
         }
     }
     
     return 1;
}

maze_generator(indeks,maze[MAX][MAX],backtrack_x[CELL],backtrack_y[CELL], x, y, n, visited)
{
	printf("Visited : %d",visited);
    if(visited < n * n)
    {
        new neighbour_valid = -1;
        new neighbour_x[4];
        new neighbour_y[4];
        new step[4];

        new x_next;
        new y_next;

        if(x - 2 > 0 && is_closed(maze, x - 2, y))  // upside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x - 2;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=1;
        }

        if(y - 2 > 0 && is_closed(maze, x, y - 2))  // leftside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y - 2;
            step[neighbour_valid]=2;
        }

        if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2))  // rightside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y + 2;
            step[neighbour_valid]=3;

        }

        if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y))  // downside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x+2;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=4;
        }

        if(neighbour_valid == -1)
        {
            // backtrack
            x_next = backtrack_x[indeks];
            y_next = backtrack_y[indeks];
            indeks--;
        }

        if(neighbour_valid!=-1)
        {
            new randomization = neighbour_valid + 1;
            new random2 = random(randomization);
            x_next = neighbour_x[random2];
            y_next = neighbour_y[random2];
            indeks++;
            backtrack_x[indeks] = x_next;
            backtrack_y[indeks] = y_next;

            new rstep = step[random2];

            if(rstep == 1)
                maze[x_next+1][y_next] = PATH;
            else if(rstep == 2)
                maze[x_next][y_next + 1] = PATH;
            else if(rstep == 3)
                maze[x_next][y_next - 1] = PATH;
            else if(rstep == 4)
                maze[x_next - 1][y_next] = PATH;
            visited++;
        }

        maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited);
    }
    
    else finished =1;
    return 1;
}

print_maze(maze[MAX][MAX],maze_size)
{
	new TempString[1000];
 	for(new a = 0; a < maze_size * 2 + 1; a++)
     {
         for(new b = 0; b < maze_size * 2 + 1; b++)
         {
             if(maze[a][b] == WALL)
                 format(TempString,sizeof(TempString),"%s#",TempString);
             else
                 format(TempString,sizeof(TempString),"%s ",TempString);
         }
         SendClientMessageToAll(0xFFFFFFFF,TempString);
         format(TempString,sizeof(TempString),"",TempString);
     }
     return 1;
}

is_closed(maze[MAX][MAX], x, y)
{
    if(maze[x - 1][y]  == WALL
       && maze[x][y - 1] == WALL
       && maze[x][y + 1] == WALL
       && maze[x + 1][y] == WALL
    )
        return 1;

    return 0;
}

public OnPlayerCommandText(playerid, cmdtext[])
{
    if(!strcmp(cmdtext, "/maze", true))
    {
	    init_maze(maze);

	    backtrack_x[indeks] = 1;
	    backtrack_y[indeks] = 1;

		while(!finished)
		{
	    	maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1);
		}
	    finished =0;
	    print_maze(maze,size);
        return 1;
    }
    return 0;
}

P.S. : That's one of my first project in PAWNO. I don't wanna be trolled

[Mauzen]

Up to which point this is shown?
printf("Visited : %d",visited);
Or isnt it shown at all? This is quite probably a buffer overflow in some array, that then crashes the function, stops execution of OnPlayerCommandText in the filterscript, and so returning unknown command.
You could either add more printf() in the code, every few lines, to find out when exactly it is crashing, or you try the crashdetect plugin. It will work best when compiling the filterscript with debug symbols, if you dont know how to do that, try searching, or ask again, ill explain it more detailled then.

[Rick]

With the printf that I made it's stopping in the maze_generator function. I removed the old printf that I made cause there were useless. Your reason (buffer overflow) is a good reason, but I tryed to find what caused this bug but I didn't find anything.

Thanks for the time that you accorded me.

[Mauzen]

Youre welcome, well, more than 5 years since then and you joined exactly the same day i did, you got my respect and my time
Ill get into that generator algorithm and will try to find the problem.

[Rick]

Perfect, I made the second part to add the generate the objects in game. But to test it we need to make work this shit :S

Good night and thanks again

[Babul]

you maze problem got my attention, too.
at first reading the init_maze snippet, i found a little enhancement already - your code:

Код:

init_maze(maze[MAX][MAX])
{
	for(new a = 0; a < MAX; a++)
	{
		for(new b = 0; b < MAX; b++)
		{
			if(a % 2 == 0 || b % 2 == 0)
			{
				maze[a][b] = 1;
			}
			else
			{
				maze[a][b] = PATH;
			}
		}
	}
	return 1;
}

1 of 2 comparements for checking if the line or row is even, are redundant, and can be transformed into a slightly faster version. i know, initialising a little labyrinth of just 30*30 cells doesnt take time anyways, but optimisations ARE are using better algorithms...

Код:

init_maze(maze[MAX][MAX])
{
	for(new a = 0; a < MAX; a+=2)
	{
		for(new b = 0; b < MAX; b+=2)
		{
			maze[a][b]=(a+b==0)?PATH:WALL;
		}
	}
	return 1;
}

...not tested btw.

[Crayder]

I know it's almost exactly 2 years from this topic's last post, but I have a question...

Has anyone succeeded in making a maze generation script?

(I have, and it worked fine. I never converted it to use objects though (it originally just laid 3Dtext on the ocean :P). Unfortunately I no longer have that script, I lost it after me and my partner gave up on it (he gave up first (well, not really, he just never talked about it anymore), I went on to complete it)).)

I plan on making one and I wanna know if anyone has any lead on a good algorithm. I used a depth-limited algorithm.