I am currently working on a custom navigation system that works on square grids.
I wanted to confirm if I was going on the correct path or not or if there are some easier ways to do this.
First what I did is create a class derived from UObject where I store the locations in a 3d array…(Could have done with a 2d array but I am going with a 3d array cause there is a chance I might have multi-layered structure)
I will just store the z values in the 3rd array and the array index of 1st and 2nd array will correspond to the grid number.
Say something like X[5].Y[2].Z*. Here the Z just stores a float which can be movable.
If the 3rd array in blank then there are no movable locations in that coordinates.
I am planning on having 4 different arrays for 4 quadrants
But one getter function to see
if the coordinates are positive and negative and get the array.
I will allow to place custom volume. The locations that have volumes are the only locations that are movable and get added to the navmesh grid data.
I will also add a custom blocking volume to prevent the navmesh data from being added at those regions.
After adding the navmesh, to detect for collisions, I plan on spawning square blocks by tracing down from the top of the volume. If the don’t collide and do some other calculations to check if a grid is movable or not.
instead of using 4 arrays it is much smoother to use only one, you only need to create a good set of coordinate to tile conversion helper functions (and xy tile to absolute tile if use an 1D array, see later). and don’t forget to mirror your Y axis
in practice I found better to use a 1D array instead of a 2D or a 3D one (tried them), because of faster/easier memory operations by memcpy and memset (they have UE4 derivatives), thus you can avoid time consuming loops. more exactly I use an 1D array to represent the 2D grid, what I later extended to contain Z related data too (when needed).
I use UStruct arrays for future possibility of multi-threading by FRunnable, found no reason to use UObject or Actor as a container (but maybe meanwhile UObjects can also be used in multi-threaded calculations I don’t know exactly).
I personally don’t use navmesh at all, but thought of it to get data from it and convert to tile information. Finally I dropped it because I have troops with different movement capabilities that would require more navmeshes…
800 dimsneional array where every dimension has size of 2 will take 6*10^240 bytes. Meaning that if copying one element takes a nanosecond, operation will take much longer than estimated current age of the universe.
I wanted to know how do you store the arrays outside the game and how do you access them inside the game?
I am assuming using a TArray might not be the most efficient way to do.
Actually my case is a lot simpler compared to the navmesh that unreal engine 4 uses.
I just require 1 navmesh in total that surrounds the whole map.
So I thought of using a 2D array…
I can just provide the X and Y index and it will get me if that location exists in the array or not. If not, then the location is not movable.
I think that might be slightly more efficient compared to manually searching the array.
I think you could make a 2D (or a pseudo 2D but indeed 1D) array that covers the game area, create a little conversion script package to convert xy coordinates to xy tiles (and vica versa), then during runtime you can very efficiently get the tile ID from coordinates (and vica versa). You need to implement:
XTileToXCoord, YTileToYCoord
XCoordToXTile, YCoordToYTile
in case of a TArray you can mark the elements as passable/blocked, it would be very fast and easy to modify if environment changes. I use TArrays.
you need to just define the 0,0 tile middle coordinates, tile size (width=height e.g. 100UU for 1m), and game area width and height in tiles. I use an UBoxComponent for this purpose.
if you decide to use an 1D array, you can use the following conversions:
AbsTilePos = XTilePos + YTilePose * GameAreaWidthInTiles;
XTilePos = AbsTilePos % GameAreaWidthInTiles; or XTilePos = FMath::FloorToInt(AbsTilePos / GameAreaHeightInTiles);
YTilePos = AbsTilePos % GameAreaHeightInTiles; or YTilePos = FMath::FloorToInt(AbsTilePos / GameAreaWidthInTiles);
I also use a box and find its extent…
Then map the elements from the top left corner of the box to the bottom right corner. Then write a function to convert the world coordinate to navmesh coordinate and vise-versa.
Also I kind of wanted to use 4 1D arrays for each Quadrant I kind of resisted doing that
Will I store this data in a class extended from USaveGame?
if you want to create it only design time in the editor, you can use an actor as the holder of the ubox and the srtucts/arrays, just mark them with UPROPERTY() and they are saved with the level. about runtime saving I have no experience yet, but would be happy if someone would share a possible solution.
When I do pathfinding I create “window maps”, i.e. units search only a portion of the whole large map because of performance, and it should be cleared and built up from the main map data for the A* very fast, where I use(d) these operation quite often.
Fortunately TArray features helpers (e.g. to avoid using AddUninitialized and FMemory::Memset or Memcpy, there exists SetNum() that creates new elements by running the constructor of the struct), but as I remember of the source, sometimes they are used internally in Array.h (FMemory::Memswap and ::Memcpy for sure).
I have not gone that far yet though…
But if I understood it, you basically create a smaller version of the large map for path finding to take place?
I have not done a good amount on A* algorithm though. Can you link me some references?
Also another thing, I need to store items and units at the grid location. Which I assume can increase in size later. So is it safe to use another TArray inside the grid structure?
I assume if the grid structure changes inside the main array would need to allocate space by shifting each element?
there is a downloadable demo with open source code package at last page, I got the idea and code snippet of the array based pseudo linked list approach of A* from here, which is finally faster than a pure linked list A* (the usual approach), and my old array based A* approach.
Its vehicle movement system was ported to Company of Heroes 1 (Adding Realistic Turn section). I do not use it as I have simple ancient/medieval warfare stuff only with a more simple approach.
you grid array system is really up to you, it is better to store grid location in units, and all important actors. then by running through them you can update the position map(s). I use static, stationary, and dynamic map arrays, depending on their update frequency. dynamic should be avoided if possible. changing the grid structure runtime is not really a good choice, especially array reallocation should be avoided runtime!
