Jump to content
  • Advertisement
Sign in to follow this  
3dmodelerguy

C# Figuring out if 2 "links" are connected in a 2D map

Recommended Posts

So I am trying to build a game with a 2d world similar to RimWorld / Prison Architect / SimAirport / etc. and trying to figure out a way to split up the world to make it easier to query for close by objects and such. The game will have a lot of items on the map and the map will be a relatively big shooting for a minimum of 200 x 200 but would like to be able to go so sizes like 300 x 300 or 350 x 350 if possible so if I want to find the closest X and there 500 X on the map, looping through each X and checking the distance and figuring out the closest one will not scale (I've tried).

Currently I have a region system that breaks the map up into 12 x 12 sections and each region keeps a list of items that need to be queries, This makes it quick to just first search the regions closest to see if they have the item being looked for and then it a region does, just checking the items in that region for distance instead of them all. This system was inspired by the video the RimWorld's developer put on basically describing this however there is one issue I am running into.

Right now my regions are fixed and if there is a structure that is fully enclosed, my region system still thinks the enclosed area is part of that region and accessible even if it is not. In the video he shows that if there are region that are cut up by impassible tiles, those regions would be split up and the 2 would not think they are connected at the point. While I have an idea on how to split the regions up by impassible tiles, how to properly makes sure the regions are not connected is a little harder for me to understand.

At this point of the video:

https://www.youtube.com/watch?v=RMBQn_sg7DA&feature=youtu.be&t=1361

He describes a system where each region store some pieces of information about each link (direction, length, starting x, and starting y) as an int using different bits for those pieces of information and while I think I have figured out how to do that, what I don't understand is how I can use that data to efficiently figure out which regions are linked without having to make sure the data structure is in a specific order so that those regions can be removed / add in any order.

This is the code I have so far:

https://repl.it/repls/TrainedCalculatingIntelligence

Is there a way with that data to be able to determine that link 1 / 2 / 3 are connected but link 4 is not?

Share this post


Link to post
Share on other sites
Advertisement

If you do not need to order items, just to get the closest one, usual aproach is "First aproached item by closest road".

In 2d your closest road would be spiral around the point of interest you seek from. Since you have distinct discreete vector space, it would be as triavial as examining each grid element for particular item to be contained, in the manner of spiralling around.

Other way, around, your post is too heavy informed to point out particular problem/s you have.

Share this post


Link to post
Share on other sites

@JohnnyCode I want to avoid checking each tile individually as if the item being looked for is really far away, that is not going to perform so well the larger the maps get and I do want to be able to support a relatively large map.

To try to better explain the problem I am trying to solve, take this image as an example:

118259517_2019-09-0114_37_28-Window-min.thumb.png.46f3028c79c8d42cab9c671eb01bf84e.png

The orange-ish outline is the active region and the gray-ish outlines are the connected regions (arrow are the edges where they connect).

Building out the regions is something I already have working (basically I split the map into 12 x 12 regions and then for each region, I do a flood fill so that if there are non-connected sections in the region, those are then broken out as separate regions.

What I am trying to figure out is what is the most efficient way of knowing what regions connect to other regions. The section of the video I linked, he talked about how he would hash certain pieces of data together (mainly the edges direction, length, starting x and y) and that would allowed him to easily connect regions and allow for the ability to only need to modify specific regions as they changed and not rebuild the entire map when something changed. That is the part I am completely lost on as I have not idea how the hash of that data can be use to determine region connectivity.

Share this post


Link to post
Share on other sites

Wild guess: You start recomputing at the point where something is changed. When you have a region, you compute the hash, and if you have that hash already, you found an existing region (assuming no duplicate hashes exist, but with big enough hashes that works (eg git does it too)).

If you didn't have that hash, it's a new region and you continue computing neighbouring regions.

Share this post


Link to post
Share on other sites

I figured out my issue in understanding what he was doing in the video. I missed the fact that he was using also using the 1 tile outside of the region in determining the link data in which case links in 2 side by side regions will always match, after understanding that (and a lot of trial and error debugging) I got the region code to work how I was wanting.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!