Jump to content
  • Advertisement

Zone division



Subscribe to our subreddit to get all the updates from the team!

A friend and I are making a rogue-lite retro procedural game. As in many procedural rogue-lite games, it will have rooms to complete but also the notion of zones. The difference between a zone and a room is that a zone is open air whilst a room is not. Rooms are connected mainly by corridors while zones are mostly naturally connected / separated by rivers and mountains.


Because we want levels with zones to be generated, we need to tame the beast that is procedural generation. How can we generate each zone itself and also clearly divide them? Until now, I had only been using the Java noise library called Joise, which is the Java community port of JTippetts' Accidental Noise Library. I needed the zone data to be generated with basis function modules, i.e. Perlin noise, but in contrast I needed a more structured approach for the zone division. Joise library does have a cell noise module that is a Worley noise. It looks like this depending on its 4 parameters (1, 0, 0, 0) : 

Image result for worley noise


Using math modules, I was able to morph that noise into something that looks like a Voronoi diagram. Here's what a Voronoi diagram should look like (never mind the colors, the important parts are the cell edges and the cell centers) :

Related image

A more aesthetic version :

Image result for voronoi


The Worley noise that I had morphed into a Voronoi-like diagram did not include the cell centers, did not include metadata about the edges and was not enough deterministic in a sense that sometimes, the edges would around 60 pixels large. I then searched for a Java Voronoi library and found this one called Voronoi-Java. With this, I was able to generate simple Voronoi diagrams :



Relaxed : 1 iteration



Relaxed : 2 iterations


The relaxation concept is actually the Lloyd's algorithm fortunately included within the library.


Now how can I make that diagram respect my level generation mechanics? Well, if we can limit an approximated number of cells within a certain resolution, that would be a good start. The biggest problem here, is that the relaxation reduces the number of cells within a restricted resolution (contrary to the global resolution) and so we need to keep that in mind.

To do that, I define a constant for the total number of sites / cells. Here's my code :

private Voronoi createVoronoiDiagram(int resolution) {
    Random random = new Random();
    Stream<Point> gen = Stream.generate(() -> new Point(random.nextDouble() * resolution, random.nextDouble() * resolution));
    return new Voronoi(gen.limit(VORONOI_SITE_COUNT).collect(Collectors.toList())).relax().relax().relax();


A brief pseudo-code of the algorithm would be the following :

  1. Create the Voronoi diagram
  2. Find the centermost zone
  3. Selects X number of zones while there are zones that respect the selection criteria
  4. Draw the border map
  5. Draw the smoothed border map

The selection criteria is applied for each edge that is connected only to one selected zone. Here's the selection criteria :

  • Is connected to a closed zone, i.e. that all its edges form a polygon
  • Does have two vertices
  • Is inclusively in the resolution's boundaries


Here's the result of a drawn border map!



In this graph, I have a restricted number of cells that follow multiple criteria and I know each edge and each cell center point.

To draw the smoothed border map, the following actions must be taken : emit colors from already drawn pixels and then apply a gaussian blur. Personally, I use the JH Labs Java Image Filters library for the gaussian blur.

With color emission only :


With color emission and a gaussian blur :


You may ask yourself why have we created a smoothed border map? There's a simple reason for this, which is that we want the borders to be gradual instead of abrupt. Let's say we want rivers or streams between zones. This gradual border will allow us to progressively increase the depth of the river and making it look more natural in contrast with the adjacent zones.

All that's left is to flood each selected cell and apply that to a zone map.


Recommended Comments

There are no comments to display.

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
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By RidiculousName
      Would any readers please explain to me the differences between FXML and CSS? I just want to create a basic GUI in JavaFX.
      For example does one work better on linux? Is one easier to learn than the other? What are their benefits and drawbacks?
    • By Androphin
      I have problems deciding some design questions.
      About the game: It's like Anno 1404 but multiplayer only
      1) Accessing GUI directly (Object interaction)

      Should the Notifier has some kind of queue or should I call it directly, because the player expects immediate response.
      A queue would maybe overkill in things of performance, if it's processor has its loop in the render method/loop.
      As of writing these lines I doesn't even know why I would have even considert choosing a queue. Searching for a solution to my problems, I came across this article http://gameprogrammingpatterns.com/event-queue.html and it made me thought if it is a good practice or needed for my problems how to wire objects and handle asynchronous tasks and object communication.
      I don't know, if its a good idea/programming style to let the ActionController do everything as a central station or to let objects do their own eventchain, like trigger a request from the ActionController, the RequestBuilder sends its request directly to the NetworkManager and the NetworkManager can directly call on the GUI.
      2) Observe game objects
      From time to time the client sends a request (carrying the actions done by the player) to the server to get a new update of the gamestate and if the actions are allowed and possible. The server calculates end send back the "cleaned" gamestate. The client receives the approved gamestate from the server and transition/interpolate from it's current state to the ones of the server, like undo not allowed actions with a message in the players notification feed, what was reverted. (not the ones shown in the image above, but an extra one)
      So there is one observer to observe the overall gamestate and little ones that observe game objects like buildings on the grid, that produce items. Is it good to use a observer pattern here?
      Can't say why, but my intuition says:
      Observers for states the player doesn't initiate directly (burning fuel, producing units over time, ...)
      Listeners for direct actions the player does (pressing a button to login, build a building, move a item on the map, pay for something, trade)
      A better example: The player wants to research "Ironswords". So he presses the button for this research. The listener notice the event and creates an observer (or subscribe that event to an existing research-observer) which observes the progress over time. If the research is finished after a certain amount of time, a notification is added to the players feed and the event unsubscribes from the observer or the observer is getting killed.
    • By Iris_Technologies
      Suppose i don't have any linker at hand but i am calling an exported function from a C++ DLL Windows, i.e. sqrt from mvcrt14.dll, how would i get just and only just the Relative Virtual Address of sqrt from that dll to simulate what linker does and convert this call to a call to such RVA on the hexcoded generated .exe file? 
      Either, how would i read the RVA of Mac, Android, iOS and Linux library formats?
    • By Neoshaman
      I'm struggling to find the correct way to make ray intersection with curve that are swept along an axis.
      In theory I thought it should be simple, I decompose the problem into component:
      - find intersection on the curve (cross section), which is easy
      - extrude that intersection point into an axis aligned line, solve the slope intersection to that line to get the final offset.

      To be sure I got it right, I'm starting with a swept 45° line centered on origin (line-plane intersection with dot product would be more efficient, but remember I'm trying to validating swiping a long a line).
      - line equation is origine + directionVector * t
      - line to line intersection equation is t = (origine1 - origine2)/(directionVector2 - directionVector1) >> assuming they are never parallel.

      So let line2dIntersection(directionVector1,origine1,directionVector2,origine2)

      Assuming the ray start on the xy plane (pseudo code):
      - I first compute the cross section into xz
      intersection1 = line2dIntersection(rayDir.xz, vector2(origine.x,0), vector2(1,1).normalize(), vector2(0,0));
      result.xz = raydir.xz * intersection1;

      -Then find the slope swipe offset into yz
      intersection2 = line2dIntersection(rayDir.yz, vector2(origine.y,0), vector2(1,0).normalize(), vector2(0,result.z));
      result.y = raydir.y * intersection2;

      But all my result are garbage. What am I doing wrong? where is the leap of logic I did?
    • By BasementJoe
      I'm sure many of you know Eric Lippert's Blog series: Wizards and Warriors. In it, he has two rules:
      A warrior can only use a sword. A wizard can only use a staff. Over the series of blogs, he tries to show you how the C# type system fails to implement those rules and what to do about it instead. He suggest the creation of a Rule class, and let the Rule system determine what can happen in the game. You can agree or disagree, that's not the point of my question. I included it because it relates to my bigger question, how would you tell the Rule class or system that the object you're trying to carry is in fact a Sword without instanceof?
      For my question, lets remove the Rule object and stick with two objects, a Wizard and Sword. A Wizard is a subclass of the abstract Character class and Sword is a subclass of the abstract Weapon class. The Character class will have a method called tryAdd();
      public final boolean tryAdd(Weapon weapon){ // Code to add Weapon } At first I thought I would use an enum to determine what object the player is attempting to add to it's inventory.
      public enum WeaponType { ReloadableWeapon // -- imagine more weapon types } public abstract class Weapon { private WeaponType wt; public Weapon(WeaponType wt) { this.wt = wt; } } public ReloadableWeapon extends Weapon{ public ReloadableWeapon() super(WeaponType.ReloadableWeapon); { } } As pointed out, it violates DRY and is a poor version of instanceof. Okay, fine, the comments suggested a Map or Collection of attributes, even this GameDev link suggested the same thing. 
      So a long the lines of this:
      public enum GameObjectAttributes{ Replenishable Destructable Health LongBlade ShortBlade Mana Health Potion Indestructible } public abstract class Weapon { private List<GameObjectAttributes> gOAttributes; // imagine a constructor :D. public final boolean containsAttribute(GameObjectAttributes attribute) { // determine if weapon contains a specific attribute. } } Suppose I had a Sword object, and the level of detail allows a Sword to be damaged and broken if hit hard enough, so my Sword object might contain Destructable and LongBlade as attributes.
      As suggested in this link, this too is a bad idea because I'm using the attributes to determine or carry out behavior with that object.
      Isn't this how OOP is supposed to work? I query an object for an answer, in this case true or false and carry out actions with that object? In this case I ask the Weapon, do you have LongBlade as an attribute? If so, the Wizard cannot add it to there inventory. The method doesn't add the weapon and returns false. 
      Even if we were to use a Rule class, at some point, we have to determine what object is being passed to the TryAdd() method, in other words, one object will have to communicate with another object to determine the object type. The link that suggests the attribute collection is a bad idea, says that a Player should implement a tryCarry method, but even that methods needs to decided if the Weapon parameter is a Sword.
      How then do you make that distinction without instanceof or a variable to decided what to do? Or How do two objects communicate with each other so that one object is aware of the other object type without violating OOP principals? Can someone provide a clean code sample?
      This problem is getting frustrating to solve because no matter what solution I come up with, someone will point out it's a bad idea, but no one can provide a solid solution to the problem. Even Eric Lippert's blog just suggests a Rule class but no example code of how to implement it. 
      What seems like a simple solution to a problem is ripped apart by veteran developers who are quick to point out something is a code smell or bad code. Sometimes I wonder why bother writing any code at all. 

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!