Hi

I have a large tile world of char world[1000][1000] describing land and sea in my gameworld ( 0 is sea, 1 is land).

Upon creating a new game I need to place "ports" on coast-tiles close to cities (land-tiles with any adjacent sea-tile).

I do this now:

pick a random city

pick a random tile which is between 10 and 15 tiles away from the city (random x and y from the city)

check if that tile is land

check if it has sea-tiles adjacent

check if the port is too close to any other port

create port

Repeat until x ports are created in the world.

This is a bit slow since i find A LOT of sea tiles or land tiles not having sea neighbours. Seems like a primitive method.

Maybe it doenst matter much since its just when starting a new campaign, but still... Any sugesstions to a better method?

Thanks

Erik

that would not find suitable coast-tiles on other islands/landmasses though...

And would it be much quicker?

Also it would find "the first" /closest suitable, which is quite different.

I have a large tile world of char world[1000][1000] describing land and sea in my gameworld ( 0 is sea, 1 is land).

Upon creating a new game I need to place "ports" on coast-tiles close to cities (land-tiles with any adjacent sea-tile).

I do this now:

pick a random city

pick a random tile which is between 10 and 15 tiles away from the city (random x and y from the city)

check if that tile is land

check if it has sea-tiles adjacent

check if the port is too close to any other port

create port

This is normaly a task for QuadTree implementation. In your case what goes slow is the O(n) runtime on your 1000*1000 map so in best case algorithm needs to look for the first element and finds a match and in worst case you need to look at all 1.000.000 elements for finding a matching node. QuadTree reudes that to O(log n) complexity because you upsample your view on the map in each step depending on the location of your city.

QuadTrees have been used for long to upsample high detail terrain mehes depending on the location of a player

yeah but around each city i just check for random tiles in a 500-900 tiles box. But true, the entire worlds is 1M tiles right now and might become larger:)

Another way is to mark coastal tiles when I create/edit the underlaying map to at least not have to do that when i place the ports:

0 sea

1 land

2 land (and also coastal)

Could be useful for other reasons as well. Otherwise i need to constantly use something like bool isTileCoastal(x,y);

Why not create a transition tile to add more flexibility to the entire system; that way you can make the comparations with that type, having in mind they were put with less restrictions that the port tile?

Why not create a transition tile to add more flexibility to the entire system; that way you can make the comparations with that type, having in mind they were put with less restrictions that the port tile?

This. Or a special set of flags in your tiles, a kind of extra map if you will.

That way, you could even refactor your search in the same sense as with deferred shading. Which would require one rather expensive (but not so much really, cache friendly) pass over the whole terrain, and comparatively little else. But it would reduce a couple of N*(N-1) problems to 0, such as "not if any other port is nearer than X" while at the same time giving you a lot of flexibility.

Something like:
for(entire map)
if(water && neighbour is land)
set(is_coast)

for(all ports)
splat circle of radius X, set no_ports_here=1

To build a port, you can then very quickly test against (is_coast & !no_ports_here) in the area around a city. Note that a big port can trivially have a bigger "no ports" influence! Just splat it bigger, the code stays identical.

As a bonus, you can draw in your no_ports_here map at will, too. For example in arctic lands or troubled waters, or where you simply don't want a port for plot / balance reasons.

For each new port created, splat into the map. Done.