• Advertisement
Sign in to follow this  

c++: getting map-tiles bordering "sea"-tiles?

This topic is 655 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

Do an expanding box edge search (xy centered on the city) til it touches water/sea (nearest) or until it is too far for a port to exist.

 

 

 

 

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

 


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

Share this post


Link to post
Share on other sites

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);

Share this post


Link to post
Share on other sites
Definitely cache the fact that a tile is coast, and do a single pass at load time/world-creation-time to determine what tiles are coastal.

You can do as you mentioned and store a new tile type, or if adding tile types sucks, just store a sparse set of coordinates like "std::set<std::pair<unsigned, unsigned>>" to hold the fact that a tile is coastal. A tile type is probably better for a handful of reasons.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement