Sign in to follow this  
Thunderzone

Unity How to update tiles based on their neighbours

Recommended Posts

Hello community i hope you can help me on this one.
I have a large hexagonal tile-map (150k tiles now might be more in future). I am working on an ecosystem simulation. Every hex has information about it's current state, and associated variables (like fertility). Tiles should be updated according to their neighboring tiles. I am facing some design and implementation problems here.
First problem is how to handle updating of two neighboring tiles. Let's say we have a tile. It's type is grass and it's fertility is 0.8, one neighbor is river, other is sand. River should rise grasses fertility, and sand should lower it, gradually until this system is balanced. If grasses fertility should drop under a certain threshold, that tile should change to sand (for example). How to design this situation in spirit of good oop.
Problem is I don't know what type is my neighbor, and so i don't know how to react to it. I could use something like double dispatch (but would two polymorphic calls incur too much overhead when world gets large?), or i could use some kind of ID system, and a switch statement. That way code could get pretty messy, as there will be more than 10 different types of tiles, and it would be nice to be able to add more later on.
Second problem is how to update a large system. Updating so much tiles could drop my frame-rate so I figured that it should be done asynchronously in a different thread. This is a [b]big [/b]issue for me because i am a total threading noob. My idea is that worker thread updates once everything, then signals the main thread, main thread detects changes and accordingly displays results (if grass is no longer grass make it a dirt).
Also is there a way to organize my data to lower cache misses. I at first used bfs algorithm to traverse entire map, but that was about 20% slower than traversing them the way they are stored in memory. Problem with updating is that i need to access neighbors data that might bee "too far" in memory.

Any kind of help is mucho appreciato. Ideas, good design principles and code are all welcome.

Share this post


Link to post
Share on other sites
If you can generalize the type of tiles interactions, you may get away by not creating a class per type. You could have your tiles provide a modification factor to various properties and make an average and then update your tile. For example, sand could reduce fertility by 0.01 every update and river increase it by 0.01, balancing themselves. You then wouldn't need to know if your neighbor is a river or sand, just how it affects your fertility.

As for your threading problem, you could simply split your tiles in chunks and split them among your worker threads instead of doing your current loop through all tiles. I wouldn't have the update be done in parallel or you will have all sorts of fun problems to deal with later on.

Share this post


Link to post
Share on other sites
As for my threading problem what kind of problems could i get into? Also could you give me a word or two about worker thread method?

About tiles, you are right we could take some time to define our abstractions better, but lets say just hypotheticaly that i have to leave some room for adding new tile types that would break current hierarchy. What would be my approach in this case. (number of tiles and fast interaction still stand)

Sorry for the lack of comment but im on my mobile :/.

Share this post


Link to post
Share on other sites
You would lose determinism when compared to single-threaded code if you use a fixed timestep approach. For example, if your update loop is :
- updateEcosystem()
- doOtherStuff()

If you take out updateEcosystem() and place it in a concurrent thread, doOtherStuff() is no longer guaranteed to work with the up to date data. It may or may not be up to date and may become up to date in the middle of the function. That means you can no longer rely on the ecosystem being up to date in your algorithms. This is where bugs come from.

What you can do instead in the updateEcosystem() function is split all the tiles into chunks. Then you send the chunks to your worker threads and wait until they complete before exiting the function. That way, you retain the same determinism than with single threaded code.

For your tiles, I'm not sure I understand the problem. It seems to me the tiles can be abstracted with a set of values from 0 to 1 and each type affects its neighbors' value in some way, probably by trying to create uniformity. If you must have more complex logic, why not keep the type as a variable and centralize all processing in some common function? You can compare the types directly without calling polymorphic functions and all that. It's not really OOP, but if that's really your bottleneck, you may have to break some rules. It's too vague to properly answer.

Share this post


Link to post
Share on other sites
What you're implementing is essentially a cellular automata. Each cell will transition to a new state, based on its current state and that of its neighbors. Automata get a little more complex when you introduce supplementary data such as the "fertility" value you mention, but it's still possible. Let's assume you have a single integer value "F" for each cell in addition to its state "S". The F-value can have different interpretations depending on its state; say, for city tiles F would be population, and for farmland tiles F would be fertility.

In these terms, you need to define the transition function that takes as input current S, current F, and current S of each adjacent tile, and outputs a new S and new F value. Now, in whatever ways you like, you need to work out your rules and define the transition functions. Keep them simple, and have them generate a large lookup table.

Finally, because a cellular automata updates atomically from one step to another, you need to keep two copies of your grid; one "current", and one "updated". After updating, swap them, making the "updated" into "current" and vice-versa. Now you can have any number of worker threads running on your grid, in whatever order ends up being best optimized; they cannot interfere with eachother, because they all read from one grid and write to non-overlapping portions of another grid.

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  

  • Partner Spotlight

  • Forum Statistics

    • Total Topics
      627653
    • Total Posts
      2978433
  • Similar Content

    • By STRATUM the Game
      Hey, everyone! This is my first post here.
      I would like to know what you think about my project called STRATUM. It's a 2D platformer that is heavily based on storytelling and boss fighting while trekking through the world.

      Everything in STRATUM takes place in the first century AD, in a world that wraps our own universe, called  The Stratum. A parallel Universe that is the home of the Christian deities . In this game you will play as a Dacian warrior, unfamiliar with everything in this world, you’ll get to know and understand The Stratum together with him.
      The main thing that I want with STRATUM is to reinvent the known lore and history of the Christian deities and realms. 
      The story is unconventional, it plays down a lot of the mysticism of Hell or Heaven and it gives it a more rational view while keeping the fantastic in it. What do I mean by that? Well, think about Hell. What do you know about it? It's a bad place where bad people go, right? Well, that's not the case in STRATUM. I don't want to describe such a world. In STRATUM, there is a reason for everything, especially for the way Hell is what it is in the game. "Hell" is called The Black Stratum in the game.
      This world is not very different from Earth, but it is governed by different natural laws.
      The story will also involve the reason why this world entered in touch with ours.

       
      What do you think about all that I said? Would you be interested in such a game? I have to say that everything is just a work of fiction made with my imagination. I do not want to offend anyone's beliefs.
      I want this to be a one man game. I have been working alone on it (this was my decision from the beginning) from art to effects to programming to music to sound effects to everything.
      I also have a youtube video HERE if you want to see the way the game moves and the way my music sounds.
      Please, any kind of feedback will be highly appreciated. If you have something bad to say, do it, don't keep it for yourself only. I want to hear anything that you don't like about my project.
       
    • By LimeJuice
      Hi, it's my first post on this forum and I would like to share the game I am working on at the moment.
      Graphics have been made with Blender3D using Cycle as a renderer and I am using Unity3D. It's a 2D game, one touch side-scrolling game for iOS and Android.
      Here some pictures, and you can have a look to the gameplay on this video :
      Feedbacks ?
      And if you want to try it, send me your email and I will add you to the beta tester list!
       
       








    • By Kirill Kot
      An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits. Active gameplay will appeal to players found of interactivity, especially lovers of quests and investigations.
      Available on:
      Gameroom (just open the web page and relax)
      AppStore
      GooglePlay
      WindowsPhone

    • By Kirill Kot
      Big Quest: Bequest. An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits.
      Mobile game, now available on Gameroom. Just open the web page and relax.
    • By Kirill Kot
      Big Quest: Bequest. An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits.
      Mobile game, now available on Gameroom. Just open the web page and relax.
  • Popular Now