javascript - 将 Javascript 示例中的暴力 Voronoi 图转换为 Python

Question

我正在尝试将生成 Voronoi 图的代码从 Javascript 转换为 Python。这是一场斗争，因为我不懂 JavaScript。我想我可以弄清楚，但我仍然遇到一些我不明白的问题。请帮我找出我的代码有什么问题。

我编写的代码只是给出了一个空白窗口。请帮我生成一个 Voronoi 图。

按顺序，我有我的代码，然后是原始代码。

这是我找到它的网站链接: Procedural Generation Wiki

我的代码:

"""
Translated from javascript example at
http://pcg.wikidot.com/pcg-algorithm:voronoi-diagram

I have included the original comments.

My own comments are preceded by two hash-tags/pound-signs.
IE
# Original Javascript comments here
## My comments here
"""

import random
import pygame
from pygame import gfxdraw

# specify an empty points array
## I will use a list.
points = []
lines = []

# get a random number in range min, max -1
## No need for our own random number function.
## Just, import random, instead.


def definePoints(numPoints, mapSize):
    # we want to take a group of points that will fit on our map at random
    for typ in range(numPoints):
        # here's the random points
        x = random.randrange(0, mapSize)
        y = random.randrange(0, mapSize)
        # "type:" decides what point it is
        # x, y: location
        # citizens: the cells in our grid that belong to this point
        ## Can't use "type:" (without quotes) in python comments
        ## Since I don't know Javascript, I dunno what he's doing here.
        ## I'm just going to append lists inside points.
        ## order is: type, x, y, citizens
        points.append([typ, x, y, []])

    # brute force-y but it works
    # for each cell in the grid
    for x in range(mapSize):
        for y in range(mapSize):
            # find the nearest point
            lowestDelta = (0, mapSize * mapSize)
            for p in range(len(points)):
                # for each point get the difference in distance
                # between our point and the current cell
                ## I split the above comment into two so
                ## it would be less than 80 characters.
                delta = abs(points[p][1] - x) + abs(points[p][2] - y)
                # store the point nearest if it's closer than the last one
                if delta < lowestDelta[1]:
                    lowestDelta = (p, delta)

            # push the cell to the nearest point
            ## Okay, here's where I start getting confused.
            ## I dunno how to do whatever he's doing in Python.
            for point in points:
                if lowestDelta[0] == point[0]:
                        activePoint = point
            dx = x - activePoint[1]
            dy = y - activePoint[2]
            # log delta in cell for drawing
            ## Again, not sure what he's doing here.
            for point in points:
                if activePoint == point:
                    point[3].append(dx)
                    point[3].append(dy)

    return points

## all comments and code from here on are mine.
def main():
    # Get points
    points = definePoints(20, 400)
    print("lines: ", lines)

    # Setup pygame screens.
    pygame.init()
    size = (400, 400)
    screen = pygame.display.set_mode(size)
    white = (255, 255, 255)

    done = False

    # Control fps of window.
    clock = pygame.time.Clock()
    fps = 40

    while not done:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                done = True

        for point in points:
            for p in point[3]:
                # draw white wherever there's a point.
                # pygame windows are black by default
                gfxdraw.pixel(screen, point[1], point[2], white)

        # controls FPS
        clock.tick(fps)

if __name__ == "__main__":
    main()

原始示例代码:

//specify an empty points array
var points = [];

//get a random number in range min, max - 1
function randRange(min, max) {
    return Math.floor(Math.random() * ((max) - min) + min);
}

function definePoints(numPoints, mapSize) {
    //we want to take a group of points that will fit on our map at random
    for(var i = 0; i < numPoints; i++) {
        //here's the random points
        var x = randRange(0, mapSize);
        var y = randRange(0, mapSize);
        //type: decides which point it is
        //x, y: location
        //citizens: the cells in our grid that belong to this point
        points.push({type: i, x: x, y: y, citizens: []});
    }
    //brute force-y but it works
    //for each cell in the grid
    for(var x = 0; x < mapSize; x++) {
        for(var y = 0; y < mapSize; y++) {
            //find the nearest point
            var lowestDelta = {pointId: 0, delta: mapSize * mapSize};
            for(var p = 0; p < points.length; p++) {
                //for each point get the difference in distance between our point and the current cell
                var delta = Math.abs(points[p].x - x) + Math.abs(points[p].y - y);
                //store the point as nearest if it's closer than the last one
                if(delta < lowestDelta.delta) {
                    lowestDelta = {pointId: p, delta: delta};
                }
            }
            //push the cell to the nearest point
            var activePoint = points[lowestDelta.pointId];
            var dx = x - activePoint.x;
            var dy = y - activePoint.y;
            //log delta in cell for drawing
            activePoint.citizens.push({
                dx: dx, 
                dy: dy
            });
        }
    }
}

definePoints(20, 40);

for(var point of points) {
        for(var citizen of point.citizens) {
            //set color of cell based on point
            //draw cell at (point.x + citizen.dx) * cellSize, (point.y + citizen.dy) * cellSize
        }
    }

Answer 1

这是修复后的版本。作者使用字典/关联数组来表示点和 lowestDelta，但它也适用于列表和元组。我只是将代码更改为“将单元格推到最近的点”并在绘图循环中添加公民点的偏移量。顺便说一句，由于您只需要绘制一次点，因此您可以在 while 循环之前执行此操作，以使代码更加高效。

import random
import pygame
from pygame import gfxdraw


def definePoints(numPoints, mapSize):
    points = []
    # we want to take a group of points that will fit on our map at random
    for typ in range(numPoints):
        # here's the random points
        x = random.randrange(0, mapSize)
        y = random.randrange(0, mapSize)
        # "type:" decides what point it is
        # x, y: location
        # citizens: the cells in our grid that belong to this point
        points.append([typ, x, y, []])

    # brute force-y but it works
    # for each cell in the grid
    for x in range(mapSize):
        for y in range(mapSize):
            # find the nearest point
            lowestDelta = (0, mapSize * mapSize)
            for p in range(len(points)):
                # for each point get the difference in distance
                # between our point and the current cell
                delta = abs(points[p][1] - x) + abs(points[p][2] - y)
                # store the point nearest if it's closer than the last one
                if delta < lowestDelta[1]:
                    lowestDelta = (p, delta)

            # push the cell to the nearest point
            activePoint = points[lowestDelta[0]]
            dx = x - activePoint[1]
            dy = y - activePoint[2]
            activePoint[3].append((dx, dy))

    return points


def main():
    pygame.init()
    size = (400, 400)
    screen = pygame.display.set_mode(size)
    white = pygame.Color('white')

    done = False
    clock = pygame.time.Clock()
    fps = 40

    points = definePoints(50, 400)

    # Draw the points before the while loop starts. No need to draw them again.
    for point in points:
        # Use different random colors for the points.
        color = (random.randrange(256), random.randrange(256),
                 random.randrange(256))
        for p in point[3]:
            # Draw the citizen points.
            # Add the offset of the citizen to the positions of the points.
            gfxdraw.pixel(screen, point[1]+p[0], point[2]+p[1], color)
        # draw white wherever there's a point.
        gfxdraw.pixel(screen, point[1], point[2], white)

    while not done:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                done = True

        clock.tick(fps)
        pygame.display.flip()


if __name__ == '__main__':
    main()