Use hash to lighten collision detection of about 1000 balls in Python (related to the new coronavirus)

Use hash to lighten collision detection of about 1000 balls in Python (related to the new coronavirus)

The Washington Post-Online Articles

This ↓ Washington Post's article on infection simulation of the new coronavirus (explanation of the phenomenon)

Why outbreaks like coronavirus spread exponentially, and![Comment 2020-08-17 161543.png] how to “flatten the curve”

Inspired by, I made a program in Python where many balls collide. (By the way, this article seems to have been the most viewed article ever online at The Washington Post.)

overshoot.py Pressing the spacebar will start the first infection. コメント 2020-08-17 163957.png

Pythonista version

Pythonisita version starts infection with spawn

スクリーンショット 2020-08-17 17.40.00.png

For the ball collision itself, see the following article of Simpson College Computer Science I used it as a reference. http://programarcadegames.com/python_examples/f.php?file=bouncing_balls.py

The problem is that when you have about 1000 balls, the movement becomes very slow. Always one ball is the other This is because the collision is judged with all the balls.

Therefore, it is only necessary to judge the collision with the balls in the vicinity, but the balls in the vicinity are decided. Use Python hash function for. When calculating the intersection judgment of rays and objects in ray tracing etc., also in Oct Tree etc. It's like splitting a space.

What is a hash?

Roughly speaking, a hash is given a variable (a string, a number, etc.) that determines the name of the box in which it will be placed. A function (can it be called a function?) Can have multiple variables. In this case, give the two-dimensional coordinates (x, y) of the ball Then, the number of the box containing the position is given from the coordinate value. For example, if x and y are 1.24 and 3.24, respectively. You can truncate after the decimal point and put it in a box named (1,3). Position (1.55, 1.99) in this box Ball also fits in a box with the same name. The formula for determining the name of the box should be considered as appropriate according to the application. This hash is provided in Python, which is convenient!

In this way, if the crossing judgment is limited to balls that are in the same box, the calculation becomes much lighter. However, in reality, the size of the ball is large, so there is a center of the ball between adjacent boxes, and Consider the possibility of collision.

The following code worked for the time being, but since Pygame is used, that module is also Must be installed. With this code, if the ball collides and collides, it will always be infected Therefore, it will be infected explosively immediately, but the incubation period, onset stage, death, antibody acquisition, number of reproductions, etc. are set. There must be.

(However, we cannot guarantee that all of this code will perfectly reflect the collision of the ball.)

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()


pythonista version

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

Use hash to lighten collision detection of about 1000 balls in Python (related to the new coronavirus)
How to use the C library in Python
Summary of how to use MNIST in Python
[Note] About the role of underscore "_" in Python
About the behavior of Model.get_or_create () of peewee in Python
Factfulness of the new coronavirus seen in Splunk
I want to use Python in the environment of pyenv + pipenv on Windows 10
I tried to automatically send the literature of the new coronavirus to LINE with Python
How to get the number of digits in Python
Let's use the open data of "Mamebus" in Python
How to use the model learned in Lobe in Python
A reminder about the implementation of recommendations in Python
To do the equivalent of Ruby's ObjectSpace._id2ref in Python
I want to use the R dataset in python
I used Python to find out about the role choices of the 51 "Yachts" in the world.
A story about trying to introduce Linter in the middle of a Python (Flask) project
How to use the __call__ method in a Python class
About the ease of Python
How to check if the contents of the dictionary are the same in Python by hash value
Comparison of how to use higher-order functions in Python 2 and 3
Quantify the degree of self-restraint required to contain the new coronavirus
About the features of Python
[Python] The status of each prefecture of the new coronavirus is only published in PDF, but I tried to scrape it without downloading it.
Summary of character string format in Python3 Whether to live with the old model or the new model
How to determine the existence of a selenium element in Python
Wrap (part of) the AtCoder Library in Cython for use in Python
How to know the internal structure of an object in Python
[Python] PCA scratch in the example of "Introduction to multivariate analysis"
[Cloudian # 9] Try to display the metadata of the object in Python (boto3)
How to check the memory size of a variable in Python
Output the contents of ~ .xlsx in the folder to HTML with Python
Feel free to change the label of the legend in Seaborn in python
Use PyCaret to predict the price of pre-owned apartments in Tokyo!
How to use the asterisk (*) in Python. Maybe this is all? ..
I wrote the code to write the code of Brainf * ck in python
[Introduction to Python] How to use the in operator in a for statement?
How to check the memory size of a dictionary in Python
Hit the New Relic API in Python to get the server status
Plot the spread of the new coronavirus
How to use SQLite in Python
In the python command python points to python3.8
How to use Mysql in python
How to use ChemSpider in Python
How to use PubChem in Python
About the basics list of Python basics
[Python / Jupyter] Translate the comment of the program copied to the clipboard and insert it in a new cell
Let's use Python to represent the frequency of binary data contained in a data frame in a single bar graph.
Create a bot that posts the number of people positive for the new coronavirus in Tokyo to Slack
Did the number of store closures increase due to the impact of the new coronavirus?
I want to batch convert the result of "string" .split () in Python
I want to explain the abstract class (ABCmeta) of Python in detail.
About Python code for simple moving average assuming the use of Numba
I tried to streamline the standard role of new employees with Python
[Introduction to Python] Thorough explanation of the character string type used in Python!
I made a program to check the size of a file in Python
I tried to predict the behavior of the new coronavirus with the SEIR model.
Folding @ Home on Linux Mint to contribute to the analysis of the new coronavirus
An example of the answer to the reference question of the study session. In python.
[Python] Summary of how to use pandas
[Introduction to Python] How to use class in Python?
Check the behavior of destructor in Python