4
\$\begingroup\$

I want to procedurally generate several points on a graph that are suitably distant from each-other. These points are meant to represent castles that are part of towns in the world-map of my game. However, I still find these points very close or touching. How can I create a set of points that are all at least a certain distance from each-other?

Here is a picture of one of the maps I've generated. The castles are black/dark grey.

enter image description here

Here is the function I'm using to generate the castles. I return a set which I iterate through in another function. This adds elements of appropriate int values to a list matrix which is iterated through with Pygame to display the map.

import random as r
import math as m


def createTiles(num, xBounds, yBounds, dist, tileSet):

    """
    Creates num amount of tuple tile locations and returns them in a set.

    :param num: int
        The amount of tile locations to be returned.

    :param xBounds: tuple of 2 ints
        The first element is the minimum x-values should be.
        The second element is the maximum x-values should be.

    :param yBounds: tuple of 2 ints
        The first element is the minimum x-values should be.
        The second element is the maximum x-values should be.

    :param dist: string or tuple of 2 strings.
        Each string contains a greater or less than sign, and a number.
        This indicates whether to cap the distance between points,
        or to keep points at least a certain distance away from each-other.
        For example, "<30" would keep points within 30 tiles of each-other.
        If a tuple is used,
        it must both cap the distance and maintain a distance.

    :param tileSet: set of tuples
        Contains already existing tile locations to be checked for distance.

    :return: set of tuples
        Returns tileSet with new tile locations.
    """
    tempSet = set()
    # handle different object types of dist
    if type(dist) == tuple or type(dist) == list:
        for d in dist:
            if d[0] == "<":
                cap = int(d[1:])
            else:
                keep = int(d[1:])
    elif type(dist) == str:
        if dist[0] == "<":
            cap = int(dist[1:])
        else:
            keep = int(dist[1:])
    else:
        keep = 0
        cap = 255

    # create tile locations and check distance against the tiles in tileSet.
    for n in range(num):
        x = r.randint(xBounds[0], xBounds[1])
        y = r.randint(yBounds[0], yBounds[1])
        for t in tileSet:
            distance = m.sqrt((x - t[0]) ** 2 + (y - t[1]) ** 2)
            while distance < keep or distance > cap or (x, y) in tileSet:
                x = r.randint(xBounds[0], xBounds[1])
                y = r.randint(yBounds[0], yBounds[1])
                distance = m.sqrt((x - t[0]) ** 2 + (y - t[1]) ** 2)

        tempSet.add((x, y))

    # Combine tileSet and tempSet.
    tileSet = tileSet.union(tempSet)
    # Check distance for all tiles in tileSet:
    for t1 in tileSet:
        for t2 in tileSet:
            distance = m.sqrt((t1[0] - t2[0]) ** 2 + (t1[1] - t2[1]) ** 2)
            while distance < keep or distance > cap:
                t1 = (r.randint(xBounds[0], xBounds[1]),
                      r.randint(yBounds[0], yBounds[1]))
                distance = m.sqrt((t1[0] - t2[0]) ** 2 + (t1[1] - t2[1]) ** 2)

    return tileSet

Thanks for looking through this. If you want any more information or anything just comment.

\$\endgroup\$

closed as off-topic by Gareth Rees, Peilonrayz, IEatBagels, Sᴀᴍ Onᴇᴌᴀ, Stephen Rauch May 3 '18 at 16:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Gareth Rees, Peilonrayz, IEatBagels, Sᴀᴍ Onᴇᴌᴀ, Stephen Rauch
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Welcome to Code Review! Does the code function correctly? If not, it isn't ready for review (see help center) and the question may be deleted. If you've tested it, I recommend that you edit to add a summary of the testing. \$\endgroup\$ – Toby Speight May 3 '18 at 15:55
  • \$\begingroup\$ @Toby Hello Toby, the image above is the result of the code I am asking for help with. The code is capable of being interpreted. Could you point me to an example of what a good summary would be? \$\endgroup\$ – LuminousNutria May 3 '18 at 16:09
  • 4
    \$\begingroup\$ The code in this post does not work as intended (it does not generate points meeting your requirements), and so it is off topic here at Code Review. But if you can figure out how to fix the problems, then you can post a new question with the fixed code. \$\endgroup\$ – Gareth Rees May 3 '18 at 16:19
  • \$\begingroup\$ Sorry about that. Thanks for letting me know. \$\endgroup\$ – LuminousNutria May 3 '18 at 16:27
1
\$\begingroup\$

There are several reasons why the code does not work.

  1. Here's the body of the first loop for generating points, in pseudo-code:

    Pick a random point (x, y)
    for t in tileSet:
        Compute distance between (x, y) and t
        while distance is wrong:
            Pick another random point (x, y)
            Recompute distance between (x, y) and t
    

    The problem here is that when you pick another random point (x, y), you only test it to see if it has the wrong distance from the particular point t. But if (x, y) has the wrong distance from one of the previous points in tileSet, you'll never find out because that will never be tested.

  2. The second loop has the same problem. Again, in pseudo-code:

    for t1 in tileSet:
        for t2 in tileSet:
            Compute distance between t1 and t2
            while distance is wrong:
                Pick another random point t1
                Recompute distance between t1 and t2
    

    The new random point t1 might be the wrong distance from one of the previous points in tileSet, but that will never be tested.

  3. Additionally, after picking the new random point t1, the code doesn't update tileSet to replace the old point with the new one.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.