hedgewars/uLandGenMaze.pas
changeset 6580 6155187bf599
parent 6490 531bf083e8db
child 8026 4a4f21070479
child 9009 f8e9d1147dd8
equal deleted inserted replaced
6579:fc52f7c22c9b 6580:6155187bf599
    89     2: dir := DIR_S;
    89     2: dir := DIR_S;
    90     3: dir := DIR_W;
    90     3: dir := DIR_W;
    91 end;
    91 end;
    92 tries := 0;
    92 tries := 0;
    93 found_cell := false;
    93 found_cell := false;
    94 if getrandom(2) = 1 then next_dir_clockwise := true
    94 if getrandom(2) = 1 then
    95 else next_dir_clockwise := false;
    95     next_dir_clockwise := true
       
    96 else
       
    97     next_dir_clockwise := false;
    96 
    98 
    97 while (tries < 5) and (not found_cell) do
    99 while (tries < 5) and (not found_cell) do
    98 begin
   100 begin
    99     if when_seen(x + dir.x, y + dir.y) = current_step then //we are seeing ourselves, try another direction
   101     if when_seen(x + dir.x, y + dir.y) = current_step then //we are seeing ourselves, try another direction
   100     begin
   102     begin
   102         //(or put a wall there if maze_inverted, but we are not doing that right now)
   104         //(or put a wall there if maze_inverted, but we are not doing that right now)
   103         if not maze_inverted and (GetRandom(braidness) = 0) then
   105         if not maze_inverted and (GetRandom(braidness) = 0) then
   104         //or just warn that inverted+braid+indestructible terrain != good idea
   106         //or just warn that inverted+braid+indestructible terrain != good idea
   105         begin
   107         begin
   106             case dir.x of
   108             case dir.x of
   107                 -1: if x > 0 then ywalls[x-1, y] := false;
   109             
   108                 1: if x < seen_cells_x - 1 then ywalls[x, y] := false;
   110                 -1:
       
   111                 if x > 0 then
       
   112                     ywalls[x-1, y] := false;
       
   113                 1:
       
   114                 if x < seen_cells_x - 1 then
       
   115                     ywalls[x, y] := false;
   109             end;
   116             end;
   110             case dir.y of
   117             case dir.y of
   111                 -1: if y > 0 then xwalls[x, y-1] := false;
   118                 -1:
   112                 1: if y < seen_cells_y - 1 then xwalls[x, y] := false;
   119                 if y > 0 then
       
   120                     xwalls[x, y-1] := false;
       
   121                 1:
       
   122                 if y < seen_cells_y - 1 then
       
   123                     xwalls[x, y] := false;
   113             end;
   124             end;
   114         end;
   125         end;
   115         if next_dir_clockwise then
   126         if next_dir_clockwise then
   116         begin
   127         begin
   117             if dir = DIR_N then
   128             if dir = DIR_N then
   134             else
   145             else
   135                 dir := DIR_S;
   146                 dir := DIR_S;
   136         end
   147         end
   137     end
   148     end
   138     else if when_seen(x + dir.x, y + dir.y) = -1 then //cell was not seen yet, go there
   149     else if when_seen(x + dir.x, y + dir.y) = -1 then //cell was not seen yet, go there
   139     begin
   150         begin
   140         case dir.y of
   151         case dir.y of
   141             -1: xwalls[x, y-1] := false;
   152             -1: xwalls[x, y-1] := false;
   142             1: xwalls[x, y] := false;
   153             1: xwalls[x, y] := false;
   143         end;
   154         end;
   144         case dir.x of
   155         case dir.x of
   149         last_cell[current_step].y := y+dir.y;
   160         last_cell[current_step].y := y+dir.y;
   150         came_from_pos[current_step] := came_from_pos[current_step] + 1;
   161         came_from_pos[current_step] := came_from_pos[current_step] + 1;
   151         came_from[current_step, came_from_pos[current_step]].x := x;
   162         came_from[current_step, came_from_pos[current_step]].x := x;
   152         came_from[current_step, came_from_pos[current_step]].y := y;
   163         came_from[current_step, came_from_pos[current_step]].y := y;
   153         found_cell := true;
   164         found_cell := true;
   154     end
   165         end
   155     else //we are seeing someone else, quit
   166     else //we are seeing someone else, quit
   156     begin
   167         begin
   157         step_done[current_step] := true;
   168         step_done[current_step] := true;
   158         found_cell := true;
   169         found_cell := true;
   159     end;
   170         end;
   160 
   171 
   161     tries := tries + 1;
   172     tries := tries + 1;
   162 end;
   173 end;
   163 if not found_cell then
   174 if not found_cell then
   164 begin
   175     begin
   165     last_cell[current_step].x := came_from[current_step, came_from_pos[current_step]].x;
   176     last_cell[current_step].x := came_from[current_step, came_from_pos[current_step]].x;
   166     last_cell[current_step].y := came_from[current_step, came_from_pos[current_step]].y;
   177     last_cell[current_step].y := came_from[current_step, came_from_pos[current_step]].y;
   167     came_from_pos[current_step] := came_from_pos[current_step] - 1;
   178     came_from_pos[current_step] := came_from_pos[current_step] - 1;
   168     if came_from_pos[current_step] >= 0 then see_cell
   179     
   169     else step_done[current_step] := true;
   180     if came_from_pos[current_step] >= 0 then
   170 end;
   181         see_cell
       
   182         
       
   183     else
       
   184         step_done[current_step] := true;
       
   185     end;
   171 end;
   186 end;
   172 
   187 
   173 procedure add_vertex(x, y: LongInt);
   188 procedure add_vertex(x, y: LongInt);
   174 var tmp_x, tmp_y: LongInt;
   189 var tmp_x, tmp_y: LongInt;
   175 begin
   190 begin
   185         pa.ar[num_vertices].y := 0;
   200         pa.ar[num_vertices].y := 0;
   186     end
   201     end
   187 end
   202 end
   188 else
   203 else
   189 begin
   204 begin
   190     if maze_inverted or (x mod 2 = 0) then tmp_x := cellsize
   205     if maze_inverted or (x mod 2 = 0) then
   191     else tmp_x := cellsize * 2 div 3;
   206         tmp_x := cellsize
   192     if maze_inverted or (y mod 2 = 0) then tmp_y := cellsize
   207     else
   193     else tmp_y := cellsize * 2 div 3;
   208         tmp_x := cellsize * 2 div 3;
       
   209         
       
   210     if maze_inverted or (y mod 2 = 0) then
       
   211         tmp_y := cellsize
       
   212     else
       
   213         tmp_y := cellsize * 2 div 3;
   194 
   214 
   195     pa.ar[num_vertices].x := (x-1)*cellsize + tmp_x;
   215     pa.ar[num_vertices].x := (x-1)*cellsize + tmp_x;
   196     pa.ar[num_vertices].y := (y-1)*cellsize + tmp_y + off_y;
   216     pa.ar[num_vertices].y := (y-1)*cellsize + tmp_y + off_y;
   197 end;
   217 end;
   198 num_vertices := num_vertices + 1;
   218 num_vertices := num_vertices + 1;
   200 
   220 
   201 procedure add_edge(x, y: LongInt; dir: direction);
   221 procedure add_edge(x, y: LongInt; dir: direction);
   202 var i: LongInt;
   222 var i: LongInt;
   203 begin
   223 begin
   204 if dir = DIR_N then
   224 if dir = DIR_N then
   205 begin
   225     begin
   206     dir := DIR_W
   226     dir := DIR_W
   207 end
   227     end
   208 else if dir = DIR_E then
   228 else if dir = DIR_E then
   209 begin
   229     begin
   210     dir := DIR_N
   230     dir := DIR_N
   211 end
   231     end
   212 else if dir = DIR_S then
   232 else if dir = DIR_S then
   213 begin
   233     begin
   214     dir := DIR_E
   234     dir := DIR_E
   215 end
   235     end
   216 else
   236 else
   217 begin
   237     begin
   218     dir := DIR_S;
   238     dir := DIR_S;
   219 end;
   239     end;
   220 
   240 
   221 for i := 0 to 3 do
   241 for i := 0 to 3 do
   222 begin
   242     begin
   223         if dir = DIR_N then
   243     if dir = DIR_N then
   224             dir := DIR_E
   244         dir := DIR_E
   225         else if dir = DIR_E then
   245     else if dir = DIR_E then
   226             dir := DIR_S
   246         dir := DIR_S
   227         else if dir = DIR_S then
   247     else if dir = DIR_S then
   228             dir := DIR_W
   248         dir := DIR_W
   229         else
   249     else
   230             dir := DIR_N;
   250         dir := DIR_N;
   231 
   251 
   232     if (dir = DIR_N) and is_x_edge(x, y) then
   252 if (dir = DIR_N) and is_x_edge(x, y) then
   233         begin
   253     begin
   234             x_edge_list[x, y] := false;
   254         x_edge_list[x, y] := false;
   235             add_vertex(x+1, y);
   255         add_vertex(x+1, y);
   236             add_edge(x, y-1, DIR_N);
   256         add_edge(x, y-1, DIR_N);
   237             break;
   257         break;
   238         end;
   258     end;
   239 
   259 
   240     if (dir = DIR_E) and is_y_edge(x+1, y) then
   260 if (dir = DIR_E) and is_y_edge(x+1, y) then
   241         begin
   261     begin
   242             y_edge_list[x+1, y] := false;
   262         y_edge_list[x+1, y] := false;
   243             add_vertex(x+2, y+1);
   263         add_vertex(x+2, y+1);
   244             add_edge(x+1, y, DIR_E);
   264         add_edge(x+1, y, DIR_E);
   245             break;
   265         break;
   246         end;
   266     end;
   247 
   267 
   248     if (dir = DIR_S) and is_x_edge(x, y+1) then
   268 if (dir = DIR_S) and is_x_edge(x, y+1) then
   249         begin
   269     begin
   250             x_edge_list[x, y+1] := false;
   270         x_edge_list[x, y+1] := false;
   251             add_vertex(x+1, y+2);
   271         add_vertex(x+1, y+2);
   252             add_edge(x, y+1, DIR_S);
   272         add_edge(x, y+1, DIR_S);
   253             break;
   273         break;
   254         end;
   274     end;
   255 
   275 
   256     if (dir = DIR_W) and is_y_edge(x, y) then
   276 if (dir = DIR_W) and is_y_edge(x, y) then
   257         begin
   277     begin
   258             y_edge_list[x, y] := false;
   278         y_edge_list[x, y] := false;
   259             add_vertex(x, y+1);
   279         add_vertex(x, y+1);
   260             add_edge(x-1, y, DIR_W);
   280         add_edge(x-1, y, DIR_W);
   261             break;
   281         break;
   262         end;
   282     end;
   263 end;
   283 end;
   264 
   284 
   265 end;
   285 end;
   266 
   286 
   267 procedure GenMaze;
   287 procedure GenMaze;
   292         maze_inverted := true;
   312         maze_inverted := true;
   293     end;
   313     end;
   294 end;
   314 end;
   295 
   315 
   296 num_cells_x := LAND_WIDTH div cellsize;
   316 num_cells_x := LAND_WIDTH div cellsize;
   297 if not odd(num_cells_x) then num_cells_x := num_cells_x - 1; //needs to be odd
   317 if not odd(num_cells_x) then
       
   318     num_cells_x := num_cells_x - 1; //needs to be odd
       
   319     
   298 num_cells_y := LAND_HEIGHT div cellsize;
   320 num_cells_y := LAND_HEIGHT div cellsize;
   299 if not odd(num_cells_y) then num_cells_y := num_cells_y - 1;
   321 if not odd(num_cells_y) then
       
   322     num_cells_y := num_cells_y - 1;
       
   323     
   300 num_edges_x := num_cells_x - 1;
   324 num_edges_x := num_cells_x - 1;
   301 num_edges_y := num_cells_y - 1;
   325 num_edges_y := num_cells_y - 1;
       
   326 
   302 seen_cells_x := num_cells_x div 2;
   327 seen_cells_x := num_cells_x div 2;
   303 seen_cells_y := num_cells_y div 2;
   328 seen_cells_y := num_cells_y div 2;
   304 
   329 
   305 if maze_inverted then
   330 if maze_inverted then
   306     num_steps := 3 //TODO randomize, between 3 and 5?
   331     num_steps := 3 //TODO randomize, between 3 and 5?
   307 else
   332 else
   308     num_steps := 1;
   333     num_steps := 1;
       
   334     
   309 SetLength(step_done, num_steps);
   335 SetLength(step_done, num_steps);
   310 SetLength(last_cell, num_steps);
   336 SetLength(last_cell, num_steps);
   311 SetLength(came_from_pos, num_steps);
   337 SetLength(came_from_pos, num_steps);
   312 SetLength(came_from, num_steps, num_cells_x*num_cells_y);
   338 SetLength(came_from, num_steps, num_cells_x*num_cells_y);
   313 done := false;
   339 done := false;
       
   340 
   314 for current_step := 0 to num_steps - 1 do
   341 for current_step := 0 to num_steps - 1 do
   315     step_done[current_step] := false;
   342     step_done[current_step] := false;
   316     came_from_pos[current_step] := 0;
   343     came_from_pos[current_step] := 0;
       
   344     
   317 current_step := 0;
   345 current_step := 0;
   318 
   346 
   319 SetLength(seen_list, seen_cells_x, seen_cells_y);
   347 SetLength(seen_list, seen_cells_x, seen_cells_y);
   320 SetLength(xwalls, seen_cells_x, seen_cells_y - 1);
   348 SetLength(xwalls, seen_cells_x, seen_cells_y - 1);
   321 SetLength(ywalls, seen_cells_x - 1, seen_cells_y);
   349 SetLength(ywalls, seen_cells_x - 1, seen_cells_y);
   360 for x := 0 to num_cells_x - 1 do
   388 for x := 0 to num_cells_x - 1 do
   361     for y := 0 to num_edges_y - 1 do
   389     for y := 0 to num_edges_y - 1 do
   362         y_edge_list[x, y] := false;
   390         y_edge_list[x, y] := false;
   363 
   391 
   364 for current_step := 0 to num_steps-1 do
   392 for current_step := 0 to num_steps-1 do
   365 begin
   393     begin
   366     x := GetRandom(seen_cells_x - 1) div LongWord(num_steps);
   394     x := GetRandom(seen_cells_x - 1) div LongWord(num_steps);
   367     last_cell[current_step].x := x + current_step * seen_cells_x div num_steps;
   395     last_cell[current_step].x := x + current_step * seen_cells_x div num_steps;
   368     last_cell[current_step].y := GetRandom(seen_cells_y);
   396     last_cell[current_step].y := GetRandom(seen_cells_y);
   369 end;
   397 end;
   370 
   398 
   371 while not done do
   399 while not done do
   372 begin
   400     begin
   373     done := true;
   401     done := true;
   374     for current_step := 0 to num_steps-1 do
   402     for current_step := 0 to num_steps-1 do
   375     begin
   403     begin
   376         if not step_done[current_step] then
   404         if not step_done[current_step] then
   377         begin
   405         begin
   412             y_edge_list[x, y] := false;
   440             y_edge_list[x, y] := false;
   413 
   441 
   414 for x := 0 to num_edges_x - 1 do
   442 for x := 0 to num_edges_x - 1 do
   415     for y := 0 to num_cells_y - 1 do
   443     for y := 0 to num_cells_y - 1 do
   416         if x_edge_list[x, y] then
   444         if x_edge_list[x, y] then
   417         begin
   445             begin
   418             x_edge_list[x, y] := false;
   446             x_edge_list[x, y] := false;
   419             add_vertex(x+1, y+1);
   447             add_vertex(x+1, y+1);
   420             add_vertex(x+1, y);
   448             add_vertex(x+1, y);
   421             add_edge(x, y-1, DIR_N);
   449             add_edge(x, y-1, DIR_N);
   422             add_vertex(NTPX, 0);
   450             add_vertex(NTPX, 0);
   423         end;
   451             end;
   424 
   452 
   425 pa.count := num_vertices;
   453 pa.count := num_vertices;
   426 
   454 
   427 RandomizePoints(pa);
   455 RandomizePoints(pa);
   428 BezierizeEdge(pa, _0_25);
   456 BezierizeEdge(pa, _0_25);
   432 DrawEdge(pa, 0);
   460 DrawEdge(pa, 0);
   433 
   461 
   434 if maze_inverted then
   462 if maze_inverted then
   435     FillLand(1, 1+off_y)
   463     FillLand(1, 1+off_y)
   436 else
   464 else
   437 begin
   465     begin
   438     x := 0;
   466     x := 0;
   439     while Land[cellsize div 2 + cellsize + off_y, x] = lfBasic do
   467     while Land[cellsize div 2 + cellsize + off_y, x] = lfBasic do
   440         x := x + 1;
   468         x := x + 1;
   441     while Land[cellsize div 2 + cellsize + off_y, x] = 0 do
   469     while Land[cellsize div 2 + cellsize + off_y, x] = 0 do
   442         x := x + 1;
   470         x := x + 1;
   443     FillLand(x+1, cellsize div 2 + cellsize + off_y);
   471     FillLand(x+1, cellsize div 2 + cellsize + off_y);
   444 end;
   472     end;
   445 
   473 
   446 MaxHedgehogs:= 32;
   474 MaxHedgehogs:= 32;
   447 if (GameFlags and gfDisableGirders) <> 0 then hasGirders:= false
   475 if (GameFlags and gfDisableGirders) <> 0 then
   448 else hasGirders := true;
   476     hasGirders:= false
       
   477 else
       
   478     hasGirders := true;
   449 leftX:= 0;
   479 leftX:= 0;
   450 rightX:= playWidth;
   480 rightX:= playWidth;
   451 topY:= off_y;
   481 topY:= off_y;
   452 hasBorder := false;
   482 hasBorder := false;
   453 end;
   483 end;