Recent

Author Topic: An example of a path search on a hexagonal map(raylib)  (Read 200 times)

Guva

  • Full Member
  • ***
  • Posts: 179
  • 🌈 ZX-Spectrum !!!
An example of a path search on a hexagonal map(raylib)
« on: April 11, 2025, 12:56:10 pm »
Code: Pascal  [Select][+][-]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6. {$IFDEF LINUX} cthreads,{$ENDIF}
  7.  Classes, SysUtils, CustApp, raylib,  Map2;
  8.  
  9. type
  10.   { TRayApplication }
  11.   TRayApplication = class(TCustomApplication)
  12.   protected
  13.     procedure DoRun; override;
  14.   public
  15.     boulderTx, bridgeTx, treeTx, grassTx, waterTx: TTexture;
  16.     boulder, hex, hewxWather, bridge, tree, pointer_: TModel;
  17.     constructor Create(TheOwner: TComponent); override;
  18.     destructor Destroy; override;
  19.   end;
  20.  
  21.   const AppTitle = 'raylib - basic window';
  22.  
  23. var
  24.    camera: TCamera;
  25.    pathStart: PMapNode = nil;
  26.    pathEnd: PMapNode = nil;
  27.   frame: Integer = 0;
  28.   _map: array[0..20, 0..15] of Integer = (
  29.    (2,2,2,0,2,2,2,2,0,2,2,0,0,2,2,2),
  30.    (2,2,0,0,0,2,2,0,0,0,2,0,0,0,0,2),
  31.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  32.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  33.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  34.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  35.    (0,0,0,0,0,0,3,3,3,3,3,0,0,0,0,0),
  36.    (0,0,0,0,3,3,3,3,3,3,3,3,0,0,0,0),
  37.    (0,0,0,3,3,3,3,3,3,3,3,3,3,0,0,0),
  38.    (0,0,3,3,3,3,3,3,3,3,3,3,3,0,0,0),
  39.    (3,4,3,3,3,3,3,3,3,3,3,3,3,0,0,0),
  40.    (0,0,3,3,3,3,3,3,3,3,3,3,3,0,0,0),
  41.    (0,0,0,3,3,3,3,3,3,3,3,3,3,0,0,0),
  42.    (0,0,0,0,3,3,3,3,3,3,3,3,0,0,0,0),
  43.    (0,0,0,0,0,0,3,3,3,3,3,0,0,0,0,0),
  44.    (0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0),
  45.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  46.    (0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0),
  47.    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
  48.    (2,0,0,0,0,2,2,0,0,0,0,0,0,0,0,2),
  49.    (2,2,0,0,2,2,2,2,2,2,0,2,0,0,2,2)
  50.  );
  51.  
  52. const
  53.  hsize = 1.004;
  54.  vsize = 1.008;
  55.  
  56.  function MouseToHex(m: TVector2): TVector2;
  57.  var
  58.    X, Z: Single;
  59.  begin
  60.    X := (((1.73205080757 / 3 * m.x) / hsize)) + hsize / 2;
  61.    Z := ((2.0 / 3 * m.y) / vsize) + vsize / 2;
  62.  
  63.    if (Trunc(Z) and 1) <> 0 then
  64.      X := X - 0.5;
  65.  
  66.    Result.x := Trunc(X);
  67.    Result.y := Trunc(Z);
  68.  end;
  69.  
  70.  
  71. { TRayApplication }
  72.  
  73. constructor TRayApplication.Create(TheOwner: TComponent);
  74. var x, y: Integer;
  75. begin
  76.   inherited Create(TheOwner);
  77.  
  78.   for y := 0 to MAPHEIGHT - 1 do
  79.   begin
  80.     for x := 0 to MAPWIDTH - 1 do
  81.     begin
  82.       mapNodes[x][y].nodeType := THexType(_map[x][y]);
  83.       mapNodes[x][y].coords.x := x;
  84.       mapNodes[x][y].coords.y := y;
  85.     end;
  86.   end;
  87.  
  88.   buildMapLinks();
  89.  
  90.   InitWindow(800, 600, AppTitle); // for window settings, look at example - window flags
  91.  
  92.   SetTargetFPS(60); // Set our game to run at 60 frames-per-second
  93.  
  94.   // Инициализация камеры
  95.    camera := Default(TCamera);  // Обнуляем структуру камеры
  96.    camera.position := Vector3Create(16.0, 16.0, -16.0);
  97.    camera.target := Vector3Create(16.0, 0.0, 16.0);
  98.    camera.up := Vector3Create(0.0, 1.0, 0.0);
  99.    camera.fovy := 45.0;
  100.    camera.projection := CAMERA_PERSPECTIVE;
  101.  
  102.  
  103.      boulder := LoadModel('data/mine.gltf.glb');
  104.      // the hex model is retextured and repurposed for those terrains
  105.      // that are simply hex shaped grass, water and similar flat ones
  106.      hex := LoadModel('data/hex.gltf.glb');
  107.      hewxWather := LoadModel('data/hex_water.gltf.glb');
  108.      bridge := LoadModel('data/hex_bridge.gltf.glb');
  109.      tree := LoadModel('data/hex_forest.gltf.glb');
  110.      pointer_ := LoadModel('data/pointer.obj');
  111.  
  112.    HideCursor();
  113. end;
  114.  
  115. procedure TRayApplication.DoRun;
  116. var
  117.   r: TRay;
  118.   rhi: TRayCollision;
  119.   curs: TVector2;
  120.   mn: PMapNode;
  121.   m: PModel;
  122.   x, y , tp: integer;
  123.   offset: Single;
  124.   tint: TColorB;
  125. begin
  126.  
  127.   while (not WindowShouldClose) do // Detect window close button or ESC key
  128.   begin
  129.     // Update your variables here
  130.     inc(frame);
  131.     UpdateCamera(@camera, CAMERA_FREE);
  132.  
  133.   r := GetMouseRay(GetMousePosition(), camera);
  134.   rhi := GetRayCollisionQuad(r,
  135.             Vector3Create(-1000, 0, -1000),
  136.             Vector3Create(1000, 0, -1000),
  137.             Vector3Create(1000, 0, 1000),
  138.             Vector3Create(-1000, 0, 1000));
  139.  
  140.   // Преобразуем координаты плоскости в координаты гексагональной карты
  141.   curs := MouseToHex(Vector2Create(rhi.point.x, rhi.point.z));
  142.  
  143.   if InMap(curs) then
  144.   begin
  145.     if IsKeyPressed(KEY_S) then
  146.     begin
  147.       pathStart := @mapNodes[Trunc(curs.x)][Trunc(curs.y)];
  148.       if Assigned(pathEnd) then
  149.         FindPath(pathStart, pathEnd);
  150.     end;
  151.  
  152.     if IsKeyPressed(KEY_E) then
  153.     begin
  154.       pathEnd := @mapNodes[Trunc(curs.x)][Trunc(curs.y)];
  155.       if Assigned(pathStart) then
  156.         FindPath(pathStart, pathEnd);
  157.     end;
  158.  
  159.     if IsKeyPressed(KEY_T) then
  160.     begin
  161.       mn := @mapNodes[Trunc(curs.x)][Trunc(curs.y)];
  162.       mn^.nodeType := THexType(Ord(mn^.nodeType) + 1);
  163.  
  164.       if mn^.nodeType > HxBridge then
  165.         // Превысили максимальный тип местности - сбрасываем
  166.         mn^.nodeType := HxGrass;
  167.  
  168.       // Необходимо перестроить связи для измененного гекса и его соседей
  169.       BuildMapLinks();
  170.       if Assigned(pathStart) and Assigned(pathEnd) then
  171.         FindPath(pathStart, pathEnd);
  172.     end;
  173.   end;
  174.     // Draw
  175.     BeginDrawing();
  176.     ClearBackground(BLACK);
  177.  
  178.     BeginMode3D(camera);
  179.  
  180.       for y := 0 to MAPHEIGHT - 1 do
  181.       begin
  182.         for x := 0 to MAPWIDTH - 1 do
  183.         begin
  184.           offset := 0;
  185.           // Нечетные строки смещены...
  186.           if Odd(y) then offset := Map2.OFFSET;
  187.         //0  if y/2 <> y/2.0 then offset := Map.OFFSET;
  188.  
  189.           m := nil;
  190.  
  191.           tp := Ord(mapNodes[x][y].nodeType);
  192.  
  193.           // Выбираем подходящую модель для типа местности
  194.           case THexType(tp) of
  195.             HxGrass:
  196.               begin
  197.                 m := @hex;
  198.                 //m^.materials[0].maps[MATERIAL_MAP_DIFFUSE].texture := grassTx;
  199.               end;
  200.             HxBoulder: m := @boulder;
  201.             HxTree: m := @tree;
  202.             HxWater:
  203.               begin
  204.                 m := @hewxWather;
  205.                 //m^.materials[0].maps[MATERIAL_MAP_DIFFUSE].texture := waterTx;
  206.               end;
  207.             HxBridge: m := @bridge;
  208.           end;
  209.  
  210.           if Assigned(m) then
  211.           begin
  212.             // Изменяем цвет в зависимости от пути и выделенных гексов
  213.             tint := WHITE;
  214.             if (x = Trunc(curs.x)) and (y = Trunc(curs.y)) then
  215.               tint := RED;
  216.             if mapNodes[x][y].onPath then
  217.               tint := ORANGE;
  218.             if pathStart = @mapNodes[x][y] then
  219.               tint := MAGENTA;
  220.             if pathEnd = @mapNodes[x][y] then
  221.               tint := GREEN;
  222.  
  223.             DrawModel(m^, Vector3Create(x*HWIDTH + offset, -1, y*HHEIGHT), 1, tint);
  224.           //  DrawModelEx(m^, Vector3Create(x * HWIDTH + offset, 0, y*HHEIGHT),
  225.             //                Vector3Create(0,1,0), 180, Vector3Create(1,1,1), tint);
  226.  
  227.  
  228.           end;
  229.         end;
  230.       end;
  231.  
  232.  
  233.       DrawModel(pointer_, rhi.point, 1, WHITE);
  234.  
  235.       EndMode3D();
  236.     EndDrawing();
  237.   end;
  238.  
  239.   // Stop program loop
  240.   Terminate;
  241. end;
  242.  
  243. destructor TRayApplication.Destroy;
  244. begin
  245.   // De-Initialization
  246.   CloseWindow(); // Close window and OpenGL context
  247.  
  248.   // Show trace log messages (LOG_DEBUG, LOG_INFO, LOG_WARNING, LOG_ERROR...)
  249.   TraceLog(LOG_INFO, 'your first window is close and destroy');
  250.  
  251.   inherited Destroy;
  252. end;
  253.  
  254. var
  255.   Application: TRayApplication;
  256. begin
  257.   Application:=TRayApplication.Create(nil);
  258.   Application.Title:=AppTitle;
  259.   Application.Run;
  260.   Application.Free;
  261. end.            
  262.  

Code: Pascal  [Select][+][-]
  1. unit Map2;
  2. {$mode objfpc}
  3.  
  4. interface
  5.  
  6. uses
  7.   SysUtils, RayLib, Classes;
  8.  
  9. const
  10.   // Размеры карты
  11.   MAPWIDTH = 21;   // Ширина карты в шестиугольниках
  12.   MAPHEIGHT = 16;  // Высота карты в шестиугольниках
  13.  
  14.   // Размеры шестиугольника
  15.   HWIDTH = 1.74;   // Ширина шестиугольника
  16.   HHEIGHT = 1.50;  // Высота шестиугольника
  17.   OFFSET = 0.87;   // Смещение для правильного расположения
  18.  
  19. type
  20.   // Типы шестиугольников
  21.   THexType = (HxGrass = 0, HxBoulder, HxTree, HxWater, HxBridge);
  22.  
  23.   // Точка на карте (координаты)
  24.   TPoint = record
  25.     x, y: Integer;
  26.   end;
  27.  
  28.   // Узел карты (шестиугольник)
  29.   PMapNode = ^TMapNode;
  30.   TMapNode = record
  31.     coords: TPoint;        // Координаты на карте
  32.     exits: array[0..5] of PMapNode; // Выходы в соседние шестиугольники (6 направлений)
  33.     passable: Boolean;     // Можно ли пройти через этот узел
  34.     nodeType: THexType;    // Тип местности
  35.     G: Integer;           // Стоимость пути от старта
  36.     H: Integer;           // Эвристическая оценка до цели
  37.     pathParent: PMapNode;  // Родительский узел в пути
  38.     onPath: Boolean;       // Признак, что узел входит в путь
  39.   end;
  40.  
  41. var
  42.   mapNodes: array[0..MAPWIDTH-1, 0..MAPHEIGHT-1] of TMapNode; // Массив узлов карты
  43.   evenDir, oddDir: array[0..5] of TPoint; // Направления для четных и нечетных строк
  44.  
  45. // Процедуры и функции
  46. procedure BuildMapLinks;    // Построение связей между узлами
  47. function Distance(ax, ay, bx, by: Integer): Single; // Расчет расстояния между узлами
  48. procedure FindPath(from, _to: PMapNode); // Поиск пути A*
  49. procedure ResetPath;        // Сброс информации о пути
  50. function InMap(c: TVector2): Boolean; // Проверка, что координаты в пределах карты
  51.  
  52. implementation
  53.  
  54. // Проверка, что координаты находятся в пределах карты
  55. function InMap(c: TVector2): Boolean;
  56. begin
  57.   if (c.x < 0) or (c.y < 0) then Exit(False);
  58.   if (c.x > MAPWIDTH-1) or (c.y > MAPHEIGHT-1) then Exit(False);
  59.   Result := True;
  60. end;
  61.  
  62. // Построение связей между узлами карты
  63. procedure BuildMapLinks;
  64. var
  65.   x, y, n, xx, yy, m, mm: Integer;
  66. begin
  67.   for y := 0 to MAPHEIGHT - 1 do
  68.   begin
  69.     for x := 0 to MAPWIDTH - 1 do
  70.     begin
  71.       // Инициализация узла
  72.       mapNodes[x][y].onPath := False;
  73.       mapNodes[x][y].H := 999;
  74.       mapNodes[x][y].G := 999;
  75.       mapNodes[x][y].passable := False;
  76.       m := Ord(mapNodes[x][y].nodeType);
  77.  
  78.       // Только травяные и мостовые узлы проходимы
  79.       if (m = Ord(HxGrass)) or (m = Ord(HxBridge)) then
  80.       begin
  81.         mapNodes[x][y].passable := True;
  82.  
  83.         // Проверка всех 6 направлений
  84.         for n := 0 to 5 do
  85.         begin
  86.           mapNodes[x][y].exits[n] := nil;
  87.           // Определение координат соседа в зависимости от четности строки
  88.           if (y mod 2) <> 0 then
  89.           begin
  90.             yy := y + evenDir[n].y;
  91.             xx := x + evenDir[n].x;
  92.           end
  93.           else
  94.           begin
  95.             yy := y + oddDir[n].y;
  96.             xx := x + oddDir[n].x;
  97.           end;
  98.  
  99.           // Если сосед в пределах карты
  100.           if InMap(Vector2Create(xx, yy)) then
  101.           begin
  102.             mm := Ord(mapNodes[xx][yy].nodeType);
  103.             // Добавляем связь, если сосед тоже проходим
  104.             if (mm = Ord(HxGrass)) or (mm = Ord(HxBridge)) then
  105.               mapNodes[x][y].exits[n] := @mapNodes[xx][yy];
  106.  
  107.             // Особые правила для мостов
  108.             if (m = Ord(HxBridge)) or (mm = Ord(HxBridge)) then
  109.               if (n <> 0) and (n <> 3) then
  110.                 mapNodes[x][y].exits[n] := nil;
  111.           end;
  112.         end;
  113.       end
  114.       else
  115.         mapNodes[x][y].passable := False;
  116.     end;
  117.   end;
  118. end;
  119.  
  120. // Расчет расстояния между двумя узлами (шестиугольная метрика)
  121. function Distance(ax, ay, bx, by: Integer): Single;
  122. var
  123.   cax, caz, cay, cbx, cbz, cby: Integer;
  124. begin
  125.   // Преобразование координат в кубическую систему
  126.   cax := ay;
  127.   caz := ax - (ay + (ay and 1)) div 2;
  128.   cay := -cax - caz;
  129.  
  130.   cbx := by;
  131.   cbz := bx - (by + (by and 1)) div 2;
  132.   cby := -cbx - cbz;
  133.  
  134.   // Расчет расстояния
  135.   Result := (Abs(cax - cbx) + Abs(cay - cby) + Abs(caz - cbz)) / 2;
  136. end;
  137.  
  138. // Функция сравнения узлов для сортировки
  139. function CompareNodes(Item1, Item2: Pointer): Integer;
  140. var
  141.   n1, n2: PMapNode;
  142. begin
  143.   n1 := PMapNode(Item1);
  144.   n2 := PMapNode(Item2);
  145.   if (n1^.G + n1^.H) > (n2^.G + n2^.H) then
  146.     Result := 1
  147.   else if (n1^.G + n1^.H) < (n2^.G + n2^.H) then
  148.     Result := -1
  149.   else
  150.     Result := 0;
  151. end;
  152.  
  153. // Сброс информации о пути во всех узлах
  154. procedure ResetPath;
  155. var
  156.   x, y: Integer;
  157. begin
  158.   for y := 0 to MAPHEIGHT - 1 do
  159.     for x := 0 to MAPWIDTH - 1 do
  160.     begin
  161.       mapNodes[x][y].onPath := False;
  162.       mapNodes[x][y].H := 999;
  163.       mapNodes[x][y].G := 999;
  164.       mapNodes[x][y].pathParent := nil;
  165.     end;
  166. end;
  167.  
  168. // Поиск пути алгоритмом A*
  169. procedure FindPath(from, _to: PMapNode);
  170. var
  171.   openList, closedList: TList; // Открытый и закрытый списки
  172.   current, successor, nn, best, n: PMapNode;
  173.   d, bestv, y, x: Integer;
  174. begin
  175.   ResetPath;
  176.   openList := TList.Create;
  177.   closedList := TList.Create;
  178.  
  179.   try
  180.     // Начинаем с начального узла
  181.     openList.Add(from);
  182.     from^.G := 2; // Базовая стоимость перемещения
  183.     from^.H := Round(Distance(from^.coords.x, from^.coords.y, _to^.coords.x, _to^.coords.y));
  184.  
  185.     // Основной цикл A*
  186.     while openList.Count > 0 do
  187.     begin
  188.       // Сортируем открытый список и берем узел с наименьшей стоимостью
  189.       openList.Sort(@CompareNodes);
  190.       current := PMapNode(openList[0]);
  191.  
  192.       // Если есть узлы с одинаковой стоимостью, выбираем случайно
  193.       if (openList.Count > 1) then
  194.       begin
  195.         nn := PMapNode(openList[1]);
  196.         if (current^.G + current^.H) = (nn^.G + nn^.H) then
  197.           if Random > 0.5 then
  198.             current := nn;
  199.       end;
  200.  
  201.       // Если достигли цели - выходим
  202.       if current = _to then Break;
  203.  
  204.       // Проверяем всех соседей текущего узла
  205.       for d := 0 to 5 do
  206.       begin
  207.         if current^.exits[d] = nil then Continue;
  208.         successor := current^.exits[d];
  209.  
  210.         // Если сосед еще не обработан и найден более короткий путь
  211.         if (closedList.IndexOf(successor) = -1) and (successor^.G > current^.G + 2) then
  212.         begin
  213.           // Удаляем из списков, если уже есть там
  214.           if closedList.IndexOf(successor) <> -1 then
  215.             closedList.Remove(successor);
  216.  
  217.           if openList.IndexOf(successor) <> -1 then
  218.             openList.Remove(successor);
  219.  
  220.           // Если узел проходим, обновляем его параметры
  221.           if successor^.passable then
  222.           begin
  223.             if successor^.G > current^.G + 2 then
  224.             begin
  225.               successor^.G := current^.G + 2;
  226.               successor^.pathParent := current;
  227.               successor^.H := Round(Distance(current^.coords.x, current^.coords.y,
  228.                                      _to^.coords.x, _to^.coords.y));
  229.               openList.Add(successor);
  230.             end
  231.             else
  232.               closedList.Add(successor);
  233.           end;
  234.         end;
  235.       end;
  236.  
  237.       // Переносим текущий узел в закрытый список
  238.       closedList.Add(current);
  239.       openList.Remove(current);
  240.     end;
  241.  
  242.     // Отмечаем найденный путь
  243.     n := _to;
  244.     while n^.pathParent <> nil do
  245.     begin
  246.       n^.onPath := True;
  247.       n := n^.pathParent;
  248.     end;
  249.     from^.onPath := True;
  250.  
  251.     // Если путь не найден, находим ближайшую к цели точку
  252.     if _to^.pathParent = nil then
  253.     begin
  254.       bestv := 999;
  255.       best := nil;
  256.       // Ищем узел с минимальной эвристической оценкой
  257.       for y := 0 to MAPHEIGHT - 1 do
  258.         for x := 0 to MAPWIDTH - 1 do
  259.         begin
  260.           if mapNodes[x][y].H < bestv then
  261.           begin
  262.             bestv := mapNodes[x][y].H;
  263.             best := @mapNodes[x][y];
  264.           end;
  265.         end;
  266.  
  267.       // Отмечаем путь до ближайшей точки
  268.       if best <> nil then
  269.       begin
  270.         n := best;
  271.         while n^.pathParent <> nil do
  272.         begin
  273.           n^.onPath := True;
  274.           n := n^.pathParent;
  275.         end;
  276.       end;
  277.     end;
  278.   finally
  279.     // Освобождаем ресурсы
  280.     openList.Free;
  281.     closedList.Free;
  282.   end;
  283. end;
  284.  
  285. initialization
  286.   // Направления для четных строк (шестиугольная сетка)
  287.   evenDir[0].x := 1;  evenDir[0].y := 0;  // Восток
  288.   evenDir[1].x := 1;  evenDir[1].y := 1;  // Юго-восток
  289.   evenDir[2].x := 0;  evenDir[2].y := 1;  // Юго-запад
  290.   evenDir[3].x := -1; evenDir[3].y := 0;  // Запад
  291.   evenDir[4].x := 0;  evenDir[4].y := -1; // Северо-запад
  292.   evenDir[5].x := 1;  evenDir[5].y := -1; // Северо-восток
  293.  
  294.   // Направления для нечетных строк (шестиугольная сетка)
  295.   oddDir[0].x := 1;  oddDir[0].y := 0;   // Восток
  296.   oddDir[1].x := 0;  oddDir[1].y := 1;   // Юго-восток
  297.   oddDir[2].x := -1; oddDir[2].y := 1;   // Юго-запад
  298.   oddDir[3].x := -1; oddDir[3].y := 0;   // Запад
  299.   oddDir[4].x := -1; oddDir[4].y := -1;  // Северо-запад
  300.   oddDir[5].x := 0;  oddDir[5].y := -1;  // Северо-восток
  301.  
  302. end.
  303.  

Guva

  • Full Member
  • ***
  • Posts: 179
  • 🌈 ZX-Spectrum !!!
Re: An example of a path search on a hexagonal map(raylib)
« Reply #1 on: April 11, 2025, 12:57:12 pm »
models for project

 

TinyPortal © 2005-2018