hedgewars/uLand.pas
changeset 3181 5c350b6c38f4
parent 3165 3ec07a7d8456
child 3224 f5f4c611bcac
--- a/hedgewars/uLand.pas	Tue Mar 30 16:01:12 2010 +0000
+++ b/hedgewars/uLand.pas	Tue Mar 30 17:17:15 2010 +0000
@@ -36,12 +36,11 @@
     playHeight, playWidth, leftX, rightX, topY, MaxHedgehogs: Longword;  // idea is that a template can specify height/width.  Or, a map, a height/width by the dimensions of the image.  If the map has pixels near top of image, it triggers border.
     LandBackSurface: PSDL_Surface;
 
-type direction = record x, y: integer; end;
-var DIR_N: direction = (x: 0; y: -1);
-var DIR_E: direction = (x: 1; y: 0);
-var DIR_S: direction = (x: 0; y: 1);
-var DIR_W: direction = (x: -1; y: 0);
-var DIR_NONE: direction = (x: 0; y: 0);
+type direction = record x, y: Longint; end;
+const DIR_N: direction = (x: 0; y: -1);
+    DIR_E: direction = (x: 1; y: 0);
+    DIR_S: direction = (x: 0; y: 1);
+    DIR_W: direction = (x: -1; y: 0);
 
 procedure initModule;
 procedure freeModule;
@@ -649,16 +648,13 @@
     medium_cell_size = 192;
     large_cell_size = 256;
     braidness = 10;
-    maze_inverted = false; //false makes more sense for now
 
 var x, y: Longint;
-    bg_color, fg_color: Longint;
     cellsize: LongInt; //selected by the user in the gui
     seen_cells_x, seen_cells_y: Longint; //number of cells that can be visited by the generator, that is every second cell in x and y direction. the cells between there are walls that will be removed when we move from one cell to another
-    start_x, start_y: Longint; //first visited cell, must be between 0 and seen_cells_x/y - 1 inclusive
     num_edges_x, num_edges_y: Longint; //number of resulting edges that need to be vertexificated
     num_cells_x, num_cells_y: Longint; //actual number of cells, depending on cell size
-    seen_list: array of array of Boolean;
+    seen_list: array of array of Longint;
     xwalls: array of array of Boolean;
     ywalls: array of array of Boolean;
     x_edge_list: array of array of Boolean;
@@ -667,13 +663,21 @@
     pa: TPixAr;
     num_vertices: Longint;
     off_y: LongInt;
+    num_steps: Longint;
+    current_step: Longint;
+    step_done: array of Boolean;
+    done: Boolean;
+    last_cell: array of record x, y: Longint; end;
+    came_from: array of array of record x, y: Longint; end;
+    came_from_pos: array of Longint;
+    maze_inverted: Boolean;
 
-function is_cell_seen(x: Longint; y: Longint): Boolean;
+function when_seen(x: Longint; y: Longint): Longint;
 begin
 if (x < 0) or (x >= seen_cells_x) or (y < 0) or (y >= seen_cells_y) then
-    is_cell_seen := true
+    when_seen := current_step
 else
-    is_cell_seen := seen_list[x, y];
+    when_seen := seen_list[x, y];
 end;
 
 function is_x_edge(x, y: Longint): Boolean;
@@ -692,11 +696,17 @@
     is_y_edge := y_edge_list[x, y];
 end;
 
-procedure see_cell(x: Longint; y: Longint);
+procedure see_cell;
 var dir: direction;
     tries: Longint;
+    x, y: Longint;
+    found_cell: Boolean;
+    next_dir_clockwise: Boolean;
+
 begin
-seen_list[x, y] := true;
+x := last_cell[current_step].x;
+y := last_cell[current_step].y;
+seen_list[x, y] := current_step;
 case GetRandom(4) of
     0: dir := DIR_N;
     1: dir := DIR_E;
@@ -704,14 +714,18 @@
     3: dir := DIR_W;
 end;
 tries := 0;
-while (tries < 5) do
+found_cell := false;
+if getrandom(2) = 1 then next_dir_clockwise := true
+else next_dir_clockwise := false;
+
+while (tries < 5) and not found_cell do
 begin
-    if is_cell_seen(x + dir.x, y + dir.y) then
+    if when_seen(x + dir.x, y + dir.y) = current_step then //we're seeing ourselves, try another direction
     begin
         //we have already seen the target cell, decide if we should remove the wall anyway
         //(or put a wall there if maze_inverted, but we're not doing that right now)
         if not maze_inverted and (GetRandom(braidness) = 0) then
-        //or just warn that inverted+braid+indestructable terrain != good idea
+        //or just warn that inverted+braid+indestructible terrain != good idea
         begin
             case dir.x of
                 -1: if x > 0 then ywalls[x-1, y] := false;
@@ -722,16 +736,30 @@
                 1: if y < seen_cells_y - 1 then xwalls[x, y] := false;
             end;
         end;
-        if dir = DIR_N then //TODO might want to randomize that
-            dir := DIR_E
-        else if dir = DIR_E then
-            dir := DIR_S
-        else if dir = DIR_S then
-            dir := DIR_W
+        if next_dir_clockwise then
+        begin
+            if dir = DIR_N then
+                dir := DIR_E
+            else if dir = DIR_E then
+                dir := DIR_S
+            else if dir = DIR_S then
+                dir := DIR_W
+            else
+                dir := DIR_N;
+        end
         else
-            dir := DIR_N;
+        begin
+            if dir = DIR_N then
+                dir := DIR_W
+            else if dir = DIR_E then
+                dir := DIR_N
+            else if dir = DIR_S then
+                dir := DIR_E
+            else
+                dir := DIR_S;
+        end
     end
-    else //cell wasn't seen yet, go there
+    else if when_seen(x + dir.x, y + dir.y) = -1 then //cell wasn't seen yet, go there
     begin
         case dir.y of
             -1: xwalls[x, y-1] := false;
@@ -741,13 +769,31 @@
             -1: ywalls[x-1, y] := false;
             1: ywalls[x, y] := false;
         end;
-        see_cell(x + dir.x, y + dir.y);
+        last_cell[current_step].x := x+dir.x;
+        last_cell[current_step].y := y+dir.y;
+        came_from_pos[current_step] := came_from_pos[current_step] + 1;
+        came_from[current_step, came_from_pos[current_step]].x := x;
+        came_from[current_step, came_from_pos[current_step]].y := y;
+        found_cell := true;
+    end
+    else //we're seeing someone else, quit
+    begin
+        step_done[current_step] := true;
+        found_cell := true;
     end;
 
     tries := tries + 1;
 end;
+if not found_cell then
+begin
+    last_cell[current_step].x := came_from[current_step, came_from_pos[current_step]].x;
+    last_cell[current_step].y := came_from[current_step, came_from_pos[current_step]].y;
+    came_from_pos[current_step] := came_from_pos[current_step] - 1;
+    if came_from_pos[current_step] >= 0 then see_cell
+    else step_done[current_step] := true;
+end;
+end;
 
-end;
 procedure add_vertex(x, y: Longint);
 var tmp_x, tmp_y: Longint;
 begin
@@ -765,9 +811,9 @@
 end
 else
 begin
-    if x mod 2 = 0 then tmp_x := cellsize
+    if maze_inverted or (x mod 2 = 0) then tmp_x := cellsize
     else tmp_x := cellsize * 2 div 3;
-    if y mod 2 = 0 then tmp_y := cellsize
+    if maze_inverted or (y mod 2 = 0) then tmp_y := cellsize
     else tmp_y := cellsize * 2 div 3;
 
     pa.ar[num_vertices].x := (x-1)*cellsize + tmp_x;
@@ -777,7 +823,7 @@
 end;
 
 procedure add_edge(x, y: Longint; dir: direction);
-var i: integer;
+var i: Longint;
 begin
 if dir = DIR_N then
 begin
@@ -844,9 +890,30 @@
 
 begin
 case cMazeSize of
-    0: cellsize := small_cell_size;
-    1: cellsize := medium_cell_size;
-    2: cellsize := large_cell_size;
+    0: begin
+        cellsize := small_cell_size;
+        maze_inverted := false;
+    end;
+    1: begin
+        cellsize := medium_cell_size;
+        maze_inverted := false;
+    end;
+    2: begin
+        cellsize := large_cell_size;
+        maze_inverted := false;
+    end;
+    3: begin
+        cellsize := small_cell_size;
+        maze_inverted := true;
+    end;
+    4: begin
+        cellsize := medium_cell_size;
+        maze_inverted := true;
+    end;
+    5: begin
+        cellsize := large_cell_size;
+        maze_inverted := true;
+    end;
 end;
 
 num_cells_x := LAND_WIDTH div cellsize;
@@ -858,6 +925,20 @@
 seen_cells_x := num_cells_x div 2;
 seen_cells_y := num_cells_y div 2;
 
+if maze_inverted then
+    num_steps := 3 //TODO randomize, between 3 and 5?
+else
+    num_steps := 1;
+SetLength(step_done, num_steps);
+SetLength(last_cell, num_steps);
+SetLength(came_from_pos, num_steps);
+SetLength(came_from, num_steps, num_cells_x*num_cells_y);
+done := false;
+for current_step := 0 to num_steps - 1 do
+    step_done[current_step] := false;
+    came_from_pos[current_step] := 0;
+current_step := 0;
+
 SetLength(seen_list, seen_cells_x, seen_cells_y);
 SetLength(xwalls, seen_cells_x, seen_cells_y - 1);
 SetLength(ywalls, seen_cells_x - 1, seen_cells_y);
@@ -867,38 +948,22 @@
 
 num_vertices := 0;
 
-(*
-TODO - Inverted maze
-if maze_inverted then
-begin
-    bg_color := 0;
-    fg_color := COLOR_LAND;
-end
-else
-begin*)
-    bg_color := COLOR_LAND;
-    fg_color := 0;
-//end;
-
 playHeight := num_cells_y * cellsize;
 playWidth := num_cells_x * cellsize;
 off_y := LAND_HEIGHT - playHeight;
 
 for x := 0 to playWidth do
     for y := 0 to off_y - 1 do
-        Land[y, x] := fg_color;
+        Land[y, x] := 0;
 
 for x := 0 to playWidth do
     for y := off_y to LAND_HEIGHT - 1 do
-        Land[y, x] := bg_color;
+        Land[y, x] := COLOR_LAND;
 
 for y := 0 to num_cells_y - 1 do
     for x := 0 to num_cells_x - 1 do
         maze[x, y] := false;
 
-start_x := GetRandom(seen_cells_x);
-start_y := GetRandom(seen_cells_y);
-
 for x := 0 to seen_cells_x - 1 do
     for y := 0 to seen_cells_y - 2 do
         xwalls[x, y] := true;
@@ -909,7 +974,7 @@
 
 for x := 0 to seen_cells_x - 1 do
     for y := 0 to seen_cells_y - 1 do
-        seen_list[x, y] := false;
+        seen_list[x, y] := -1;
 
 for x := 0 to num_edges_x - 1 do
     for y := 0 to num_cells_y - 1 do
@@ -919,11 +984,29 @@
     for y := 0 to num_edges_y - 1 do
         y_edge_list[x, y] := false;
 
-see_cell(start_x, start_y);
+for current_step := 0 to num_steps-1 do
+begin
+    x := GetRandom(seen_cells_x - 1) div num_steps;
+    last_cell[current_step].x := x + current_step * seen_cells_x div num_steps;
+    last_cell[current_step].y := GetRandom(seen_cells_y);
+end;
+
+while not done do
+begin
+    done := true;
+    for current_step := 0 to num_steps-1 do
+    begin
+        if not step_done[current_step] then
+        begin
+            see_cell;
+            done := false;
+        end;
+    end;
+end;
 
 for x := 0 to seen_cells_x - 1 do
     for y := 0 to seen_cells_y - 1 do
-        if seen_list[x, y] then
+        if seen_list[x, y] > -1 then
             maze[(x+1)*2-1, (y+1)*2-1] := true;
 
 for x := 0 to seen_cells_x - 1 do
@@ -971,12 +1054,17 @@
 
 DrawEdge(pa, 0);
 
-x := 0;
-while Land[cellsize div 2 + cellsize + off_y, x] = bg_color do
-    x := x + 1;
-while Land[cellsize div 2 + cellsize + off_y, x] = fg_color do
-    x := x + 1;
-FillLand(x+1, cellsize div 2 + cellsize + off_y);
+if maze_inverted then
+    FillLand(1, 1+off_y)
+else
+begin
+    x := 0;
+    while Land[cellsize div 2 + cellsize + off_y, x] = COLOR_LAND do
+        x := x + 1;
+    while Land[cellsize div 2 + cellsize + off_y, x] = 0 do
+        x := x + 1;
+    FillLand(x+1, cellsize div 2 + cellsize + off_y);
+end;
 
 MaxHedgehogs:= 32;
 if (GameFlags and gfDisableGirders) <> 0 then hasGirders:= false
@@ -984,7 +1072,7 @@
 leftX:= 0;
 rightX:= playWidth;
 topY:= off_y;
-hasBorder := true;
+hasBorder := false;
 end;
 
 procedure GenLandSurface;