Download

What would be the best way to store navigation data for a round planet?

Hello, i am creating an AI class for a RTS game that will be set on a round planet, the problem is, i can’t use navmeshes or any inbuilt AI stuff from the engine, and i have to build it from the ground up.

The planet has a diameter of 100 kilometers, so i decided to make it using a cube sphere, and then create 6 quadtrees, one for each side of the cube, each quadtree would be 157 x 157 kilometers, and would be subdivided until each cell is 50 x 50 cm, so i can create a fairly detailed relief for it’s landscape.

But if i am to store the cost for each cell, i should have to store more than 50 GBs of data for each cube face, ad that’s just impractical, i’ve seen games that store that kind of information using way less space, so my question is, what would be the best way to store cost maps? Besides using textures, because if i use textures, the same problem arrives, i would need 100k textures of 1k resolution for each cube face.

Another way is to calculate cost on the fly, without storing anything, which would be a lot faster and less resource-intensive, but, i have no way of telling if an obstacle is intersecting a cell, without using line tracing, and that is just too expensive for long distances.

In order to simplify the problem i created a smaller version using a single plane of 32 x 32 cells, each cell is 50 x 50 cm, so it has an area of 512 square meters, it’s way smaller and it still presents the problem of finding if obstacles are intersecting cells, and finding which cells are within the obstacle.

The method i’m using to calculate cost on the fly is simply taking the normal of each cell and taking it’s dot product in relation to the Up vector, so this gives me a relief map that i can use to calculate whether the unit can traverse the region, or not, but, i have no clue as to how to calculate cost from obstacles like buildings and other units and such. Any ideas on that?

Thanks in advance.