CODEWITHSUNDEEP
python-3.xpygame
Alexander Wolters
Alexander Wolters

Reputation: 152

Get the nearest unvisited point?

I have set up a pygame window with 10 points in it,and now I am trying to have each point connect to the closest point that no point before has connected to. Now, when I run this point, some points form closed loops, while there should not be such except one that should then contain all the points.

What it does look like

for p in points:
    bestdist=math.inf
    for q in openset:
        if(points[p]!=openset[q]):
            cdist=dist(points[p],openset[q])
            if cdist<bestdist:
                bestdist=cdist
                b=q
    pygame.draw.line(DISPLAYSURF, RED, points[p] ,points[b], 2)
    openset.pop(b,None)
    pygame.display.update()

Upvotes: 1

Views: 47

Answers (1)

skrx
skrx

Reputation: 20438

Take a look at this example. I just append the nearest point to the connected_points list and remove it from the openset. The current point is just the last added point: current_point = connected_points[-1].

import math
import random
import pygame as pg


def dist(p1, p2):
    return math.hypot(p2[0]-p1[0], p2[1]-p1[1])


def main():
    screen = pg.display.set_mode((640, 480))
    clock = pg.time.Clock()
    points = [(random.randrange(640), random.randrange(480))
              for _ in range(10)]
    openset = set(points)
    connected_points = [random.choice(points)]
    openset.remove(connected_points[-1])

    done = False

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

        if openset:
            bestdist = math.inf
            current_point = connected_points[-1]
            for point in openset:
                cdist = dist(current_point, point)
                if cdist < bestdist:
                    bestdist = cdist
                    nearest_point = point

            connected_points.append(nearest_point)
            openset.remove(nearest_point)

        screen.fill((30, 30, 30))
        for p in points:
            pg.draw.circle(screen, (100, 140, 100), p, 5)
        if len(connected_points) >= 2:
            pg.draw.lines(screen, (150, 50, 50), False, connected_points, 2)

        pg.display.flip()
        pg.time.wait(500)
        clock.tick(30)


if __name__ == '__main__':
    pg.init()
    main()
    pg.quit()

Upvotes: 1

Related Questions