Utilisez le hachage pour alléger le jugement de collision d'environ 1000 balles en Python (lié au nouveau virus corona)
Utilisez le hachage pour alléger le jugement de collision d'environ 1000 balles en Python (lié au nouveau virus corona)
Articles du Washington Post-Online
Cet article du ↓ Washington Post sur la simulation d'une nouvelle infection par le virus corona (explication du phénomène)
Inspiré par, j'ai créé un programme en Python où de nombreuses balles se heurtent. (À propos, cet article semble avoir été l'article le plus consulté jamais publié en ligne au Washington Post.)
overshoot.py
Appuyez sur la touche espace pour lancer la première infection.
Version Pythonista
La version de Pythonisita démarre l'infection avec spawn
Pour la collision de balle elle-même, voir l'article suivant de Simpson College Computer Science Je l'ai utilisé comme référence. http://programarcadegames.com/python_examples/f.php?file=bouncing_balls.py
Le problème est que lorsque vous avez environ 1000 balles, le mouvement devient très lent. Toujours une balle est l'autre C'est parce que la collision est jugée avec toutes les balles.
Par conséquent, il suffit de juger de la collision avec les balles proches, mais les balles proches sont décidées. Utilisez la fonction de hachage Python pour. Lors du calcul du jugement d'intersection des rayons et des objets en course tardive, etc., également dans Oct Tree etc. C'est comme diviser l'espace.
Qu'est-ce qu'un hash?
En gros, un hachage est une variable donnée (chaîne, nombre, etc.) qui détermine le nom de la boîte dans laquelle il sera placé. Il peut y avoir plusieurs variables dans une fonction (peut-elle être appelée une fonction?). Dans ce cas, donnez les coordonnées bidimensionnelles (x, y) de la balle Ensuite, le numéro de la boîte contenant la position est donné à partir de la valeur des coordonnées. Par exemple, si x et y valent respectivement 1,24 et 3,24. Vous pouvez tronquer après le point décimal et le mettre dans une case nommée (1,3). Position (1,55, 1,99) dans cette case Ball va également dans une boîte avec le même nom. La formule pour déterminer le nom de la boîte doit être considérée comme appropriée en fonction de l'application. Ce hachage est fourni en Python, donc c'est pratique!
De cette manière, si le jugement de croisement est limité aux balles qui sont dans la même case, le calcul devient beaucoup plus léger. Cependant, comme la balle est en fait grande, il y a un centre de la balle entre les cases adjacentes, et Considérez la possibilité d'une collision.
Le code suivant a fonctionné pour le moment, mais comme Pygame est utilisé, ce module est également Doit être installé. Avec ce code, si la balle entre en collision et entre en collision, elle sera toujours infectée Il sera donc infecté de manière explosive immédiatement, mais définissez la période de latence, le stade d'apparition, la mort, l'acquisition d'anticorps, le nombre de reproductions, etc. Il doit y avoir.
(Cependant, nous ne pouvons pas garantir que tout ce code reflète parfaitement la collision de la balle.)
code
overshoot.py
import pygame
import random
import math
#import numpy as np
#import copy
# Define colors
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
BLUE = (90, 90, 180)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
GREY = (50, 50, 255)
SCREEN_WIDTH = 700
SCREEN_HEIGHT = 650
start_time = pygame.time.get_ticks()
class Ball:
"""
Class to keep track of a ball's location and vector.
"""
def __init__(self):
# radius
self.r = 4
# diameter
self.d = self.r * 2
# position
self.x = 0
self.y = 0
# velocity
self.vx = 0
self.vy = 0
# color
self.color = (0, 255, 0)
# neighbour
self.px = False
self.mx = False
self.py = False
self.my = False
def make_ball():
"""
Function to make a new, random ball.
"""
ball = Ball()
# Starting position of the ball.
# Take into account the ball size so we don't spawn on the edge.
ball.x = random.randrange(ball.d, SCREEN_WIDTH - ball.d)
ball.y = random.randrange(ball.d, SCREEN_HEIGHT - ball.d - 200)
# Speed and direction of rectangle
ball.vx = float(random.randrange(-2, 2)) * 0.2
ball.vy = float(random.randrange(-2, 2)) * 0.2
return ball
def main():
"""
main program.
"""
pygame.init()
xval = 0
bcount = 0
#redcount = 0
# Set the height and width of the screen
size = [SCREEN_WIDTH, SCREEN_HEIGHT]
screen = pygame.display.set_mode(size)
pygame.display.set_caption("OverShoot")
# Loop until the user clicks the close button.
done = False
# Used to manage how fast the screen updates
clock = pygame.time.Clock()
# dictionary
results = {}
cell_size = 40
ball_amount = 800
# Spawn many balls
for i in range(ball_amount):
ball = make_ball()
results.setdefault((int(ball.x/cell_size), int(ball.y/cell_size)), []).append(ball)
print(len(results.keys()))
#print(results)
screen.fill((20,20,20), rect=(0,SCREEN_HEIGHT - 250, SCREEN_WIDTH,SCREEN_HEIGHT))
# -------- Main Program Loop -----------
while not done:
# --- Event Processing
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True
elif event.type == pygame.KEYDOWN:
# Space bar! Spawn a new ball.
if event.key == pygame.K_SPACE:
ball = make_ball()
ball.color = RED
results.setdefault((int(ball.x/cell_size), int(ball.y/cell_size)), []).append(ball)
#
if event.key == pygame.K_g:
ball = make_ball()
ball.color = (255,0,255)
results.setdefault((int(ball.x/cell_size), int(ball.y/cell_size)), []).append(ball)
# --- Drawing
# Set the screen background
screen.fill(GREY, rect=(0,0,SCREEN_WIDTH,SCREEN_HEIGHT - 200 + ball.d))
# Draw the balls
cresults = {}
for ky in results:
blist = results[ky]
blist2 = blist.copy()
#
for bl in blist:
blist2.remove(bl)
if bl.px:
k = (ky[0]+1,ky[1])
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.mx:
k = (ky[0]-1,ky[1])
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.py:
k = (ky[0],ky[1]+1)
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.my:
k = (ky[0],ky[1]-1)
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.px and bl.py:
k = (ky[0]+1,ky[1]+1)
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.mx and bl.py:
k = (ky[0]-1,ky[1]+1)
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.px and bl.my:
k = (ky[0]+1,ky[1]-1)
if k in results:
ek = results[k]
blist2.extend(ek)
if bl.mx and bl.my:
k = (ky[0]-1,ky[1]-1)
if k in results:
ek = results[k]
blist2.extend(ek)
#
for bl2 in blist2:
#if bl == bl2:
# continue
# Circle Intersect
sqDist = (bl2.x-bl.x)*(bl2.x-bl.x)+(bl2.y-bl.y)*(bl2.y-bl.y)
#if sqDist > 0 and sqDist <= ((BALL_SIZE)+(BALL_SIZE)):
#print(sqDist, math.sqrt(sqDist))
if sqDist > 0 and sqDist <= (bl.d*bl.d):
# detect collision
dist = math.sqrt(sqDist)
# vCollison
vc = ([bl2.x-bl.x, bl2.y-bl.y])
# vCollisonNorm
vcn = ([vc[0]/dist, vc[1]/dist])
# vRelativeVelocity
vrv = ([bl.vx-bl2.vx, bl.vy-bl2.vy])
speed = vrv[0]*vcn[0] + vrv[1]*vcn[1]
#print(speed)
if speed > 0:
bl.vx -= speed * vcn[0]
bl.vy -= speed * vcn[1]
bl2.vx += speed * vcn[0]
bl2.vy += speed * vcn[1]
#
#infection
if bl.color == RED and bl2.color != RED:
bl2.color = RED
bcount += 1
if bl2.color == RED and bl.color != RED:
bl.color = RED
bcount += 1
#
col = bl.color
pygame.draw.circle(screen, col, [round(bl.x), round(bl.y)], bl.r)
bl.x += bl.vx
bl.y += bl.vy
# avoid line y
if bl.y > SCREEN_HEIGHT - 200 + bl.r:
bl.y = SCREEN_HEIGHT - 200
bl.vy = -bl.vy
if bl.y < bl.r :
bl.y = bl.r
bl.vy = -bl.vy
if bl.x < bl.r:
bl.x = bl.r
bl.vx = -bl.vx
if bl.x <= 0 :
bl.vx = 0.1
if bl.x > SCREEN_WIDTH - bl.r:
bl.x = SCREEN_WIDTH - bl.r
bl.vx = -bl.vx
#
#Bounce the ball if needed
if bl.y > SCREEN_HEIGHT - 200 or bl.y < bl.r:
bl.vy *= -1
if bl.x > SCREEN_WIDTH - bl.r or bl.x < bl.r:
bl.vx *= -1
# set key and get hash and append
cresults.setdefault((int(bl.x/cell_size), int(bl.y/cell_size)), []).append(bl)
#
# check neighbour with new key
bl.px = int((bl.x+bl.r)/cell_size) > int(bl.x/cell_size)
bl.mx = int((bl.x-bl.r)/cell_size) < int(bl.x/cell_size)
bl.py = int((bl.y+bl.r)/cell_size) > int(bl.y/cell_size)
bl.my = int((bl.y-bl.r)/cell_size) < int(bl.y/cell_size)
results.clear()
results.update(cresults)
# show stat
timepassed = pygame.time.get_ticks()-start_time
if timepassed % 12 == 0:
if bcount > 0 and bcount < ball_amount:
pygame.draw.line(screen,(200,0,0),(xval*2,SCREEN_HEIGHT-10),(xval*2,SCREEN_HEIGHT-int(bcount/5)-10),2)
xval += 1
#for res in results:
# a = results[res]
# for bl in a:
# pygame.draw.circle(screen, WHITE, [round(bl.x), round(bl.y)], BALL_SIZE)
# break
# Go ahead and update the screen with what we've drawn.
clock.tick(60)
pygame.display.flip()
# Close everything down
pygame.quit()
if __name__ == "__main__":
main()
version pythonista
overshoot.py
import ui
from scene import *
import random
import math
import time
import sys
import os
# Define colors
BLACK = (0, 0, 0)
WHITE = (1, 1, 1)
BLUE = (0.5, 0.5, 0.8)
GREEN = (0, 1, 0)
RED = (1, 0, 0)
GREY = (0.5, 0.5, 0.5)
CELL_SIZE = 20
BALL_AMOUNT = 800
class Ball:
"""
Class to keep track of a ball's location and vector.
"""
def __init__(self):
# radius
self.r = 3
# diameter
self.d = self.r * 2
# position
self.x = 0
self.y = 0
# velocity
self.vx = 0
self.vy = 0
# color
self.color = (0, 1, 0)
# neighbour
self.nb = (False,False,False,False)
def make_ball(self):
"""
Function to make a new, random ball.
"""
ball = Ball()
# Starting position of the ball.
# Take into account the ball size so we don't spawn on the edge.
ball.x = random.randrange(ball.d, self.size.width - ball.d)
ball.y = random.randrange(270, self.size.height- ball.d-200)
# Speed and direction of rectangle
ball.vx = float(random.randrange(-2, 2)) * 0.2
ball.vy = float(random.randrange(-2, 2)) * 0.2
return ball
def button_tapped(sender):
#print('hhh')
os.abort()
class MyScene2(Scene):
def setup(self):
self.val = (0,0)
self.bar = []
self.last = 0
def add(self):
self.bar.append(self.val[1])
print(self.val[1])
def draw(self):
#print(self.val)
background(0.5,0.5,0.5)
fill(0.9,0.0,0.5)
#
for i in range(len(self.bar)):
rect(40+i*2, 4, 2, 4+self.bar[i]/4)
class MyScene(Scene):
def setup(self):
self.startTime = time.time()
self.xval = 0
self.bcount = 0
self.last = 0
#self.MySprite = SpriteNode(color = 'red', size = (32,32), parent = self)
#self.spot=ShapeNode(path=ui.Path.rect (100,0,50 ,30),parent=self)
#self.spot.position = (200,500)
self.results = {}
self.cell_size = CELL_SIZE
self.ball_amount = BALL_AMOUNT
# Spawn many balls
for i in range(self.ball_amount):
ball = make_ball(self)
self.results.setdefault((int(ball.x/self.cell_size), int(ball.y/self.cell_size)), []).append(ball)
# red ball
#aball = make_ball(self)
#aball.color = RED
#self.results.setdefault((int(ball.x/self.cell_size), int(ball.y/self.cell_size)), []).append(aball)
print("cell number = ",len(self.results.keys()))
# disp hashmap data
cnt = 0
ad = 0
ocl = 0
for aky in self.results.keys():
ad += len(aky)
cnt += 1
if len(aky) == 1:
ocl += 1
print("balls / cell = ", ad/cnt)
print("1 ball cell = ", ocl)
# scene view for stat
self.sv = SceneView(frame=(0, self.view.height-250,self.view.width,250),flex='WH')
self.s2 = MyScene2()
self.sv.scene = self.s2
self.view.add_subview(self.sv)
self.sv.border_color = (0.9,0.6,0.7)
self.sv.border_width = 3
#
button = ui.Button()
button.frame = (110,100,120,30)
button.action = self.button_tapped
button.title = 'spawn'
button.background_color = (0.6,0.3,0.5)
button.tint_color = ('white')
self.view.add_subview(button)
def button_tapped(self,sender):
#print('hhhgggg')
aball = make_ball(self)
aball.r= 3
aball.d = 60
aball.color = RED
self.results.setdefault((int(aball.x/self.cell_size), int(aball.y/self.cell_size)), []).append(aball)
def draw(self):
cell_size = CELL_SIZE
#bcount = self.bcount
background(0, 0, 150)
fill(110,10,10)
tint(200,5,5)
# Draw the balls
#self.cresults = {}
cresults = {}
for ky in self.results:
blist = self.results[ky]
blist2 = blist.copy()
#
for bl in blist:
blist2.remove(bl)
skip = True
if bl.nb[0] and bl.nb[1]:
k = (ky[0]+1,ky[1]+1)
if k in self.results:
blist2.extend(self.results[k])
skip = False
if skip and bl.nb[2] and bl.nb[1]:
k = (ky[0]-1,ky[1]+1)
if k in self.results:
blist2.extend(self.results[k])
skip = False
if skip and bl.nb[0] and bl.nb[2]:
k = (ky[0]+1,ky[1]-1)
if k in self.results:
blist2.extend(self.results[k])
skip = False
if skip and bl.nb[2] and bl.nb[2]:
k = (ky[0]-1,ky[1]-1)
if k in self.results:
blist2.extend(self.results[k])
#
if bl.nb[0]:
k = (ky[0]+1,ky[1])
if k in self.results:
blist2.extend(self.results[k])
if bl.nb[2]:
k = (ky[0]-1,ky[1])
if k in self.results:
blist2.extend(self.results[k])
if bl.nb[1]:
k = (ky[0],ky[1]+1)
if k in self.results:
blist2.extend(self.results[k])
if bl.nb[3]:
k = (ky[0],ky[1]-1)
if k in self.results:
blist2.extend(self.results[k])
#
for bl2 in blist2:
#if bl == bl2:
# continue
# Circle Intersect
sqDist = (bl2.x-bl.x)*(bl2.x-bl.x)+(bl2.y-bl.y)*(bl2.y-bl.y)
#if sqDist > 0 and sqDist <= ((BALL_SIZE)+(BALL_SIZE)):
#print(sqDist, math.sqrt(sqDist))
if sqDist > 0 and sqDist <= ((bl.r+bl2.r)*(bl.r+bl2.r)):
# detect collision
dist = math.sqrt(sqDist)
# vCollison
vc = ([bl2.x-bl.x, bl2.y-bl.y])
# vCollisonNorm
vcn = ([vc[0]/dist, vc[1]/dist])
# vRelativeVelocity
vrv = ([bl.vx-bl2.vx, bl.vy-bl2.vy])
speed = vrv[0]*vcn[0] + vrv[1]*vcn[1]
#print(speed)
if speed > 0:
bl.vx -= speed * vcn[0]
bl.vy -= speed * vcn[1]
bl2.vx += speed * vcn[0]
bl2.vy += speed * vcn[1]
#
#infection
if bl.color == RED and bl2.color != RED:
bl2.color = RED
self.bcount += 1
if bl2.color == RED and bl.color != RED:
bl.color = RED
self.bcount += 1
#
# draw shape
fill(bl.color)
ellipse(int(bl.x)-bl.r, int(bl.y)-bl.r, bl.r*2, bl.r*2)
bl.x += bl.vx
bl.y += bl.vy
# avoid line y
if bl.y > self.size.height - 200 + bl.r:
bl.y = self.size.height - 200
bl.vy = -bl.vy
if bl.y < bl.r :
bl.y = bl.r
bl.vy = -bl.vy
if bl.x < bl.r:
bl.x = bl.r
bl.vx = -bl.vx
if bl.x <= 0 :
bl.vx = 0.1
if bl.x > self.size.width - bl.r:
bl.x = self.size.width - bl.r
bl.vx = -bl.vx
#
#Bounce the ball if needed
if bl.y > self.size.height - 200 or bl.y < bl.r + 260:
bl.vy *= -1
if bl.x > self.size.width - bl.r or bl.x < bl.r:
bl.vx *= -1
# set key and get hash and append
cresults.setdefault((int(bl.x/cell_size), int(bl.y/cell_size)), []).append(bl)
#
# check neighbour with new key
px = int((bl.x+bl.r)/cell_size) > int(bl.x/cell_size)
mx = int((bl.x-bl.r)/cell_size) < int(bl.x/cell_size)
py = int((bl.y+bl.r)/cell_size) > int(bl.y/cell_size)
my = int((bl.y-bl.r)/cell_size) < int(bl.y/cell_size)
bl.nb =(px,py,mx,my)
self.results.clear()
self.results.update(cresults)
#print((selfself.spot.position = (100,800).now-dt.now).seconds))
timepassed = time.time()-self.startTime
#print(int(timepassed))
if int(timepassed) != self.last and self.ball_amount > self.bcount:
self.s2.add()
self.s2.val = (self.xval, self.bcount)
self.last = int(timepassed)
self.xval += 1
s=MyScene()
#Scene.run(s, show_fps=True)
main_view = ui.View()
scene_view = SceneView(frame=main_view.bounds, flex='WH')
main_view.title = 'OverShoot'
main_view.tint_color = (0,0,0)
main_view.add_subview(scene_view)
scene_view.scene = s
button = ui.Button()
button.frame = (10,100,main_view.width-20,30)
button.action = button_tapped
button.title = 'quit'
button.background_color = (0.6,0.3,0.5)
button.tint_color = ('white')
main_view.add_subview(button)
#scene_view.add_subview(sv)
#sv.background_color = (1,0,0)
main_view.present(hide_title_bar=False, animated=False)
Recommended Posts