The Swift Priority Queue Tutorial.
Last time we ended with a discussion of the practical implementation of a Priority Queue.
This time we’ll see it in action.
Download the source to follow along: https://github.com/fastestapp/Collide
The Priority Queue can solve a difficult problem: How to handle collisions between 20 particles on a screen where in reality you need to calculate the possible collisions between each particle and every other particle. This is approximately 20 * 19 collisions.
Today we’ll consider only the simple case where 20 particles can collide with 4 walls.
We’ll use a TimelineView to update our SwiftUI app every screen refresh. And we’ll only examine particles that bounce off walls — we won’t yet consider collisions between particles.
Consider each of the seven files in the project in turn.
1. CollideApp.swift This is the boilerplate app file.
You can look at other resources if you want details on this file.
2. ContentView.swift. This contains the TimelineView and the Canvas for drawing.
We’ll consider each of these in turn. They are each valuable things to learn.
In SwiftUI we can create a view that updates itself according to a schedule. This is a TimelineView. The main variable we want to control in a TimelineView is the schedule. The schedule is the frequency of view refresh.
The TimelineView schedule can be set to update in a continuous fashion or at custom intervals.
In this project, we want to update the schedule using a default frequency optimal for animations.
Consider our ContentView:
import SwiftUI
struct ContentView: View {
@StateObject var particleSystem = ParticleSystem()
var body: some View {
ZStack {
Color(.blue)
TimelineView(.animation) { timeline in
Canvas { context, size in
particleSystem.update(date: timeline.date)
let baseTransform = context.transform
for particle in particleSystem.particles {
context.translateBy(x: particle.x, y: particle.y)
context.draw(particleSystem.image, at: .zero)
context.transform = baseTransform
}
}
}
VStack {
PriorityQueueCount()
Spacer()
.frame(width: 100, height: 50)
}
}
.ignoresSafeArea()
.statusBarHidden()
.onAppear{
particleSystem.startup()
}
}
}
The code from this file shows how we create a TimelineView with the .animation schedule. And it shows how we send a ‘timeline’ value to the closure. This value contains the timeline.date that we capture to update our particle system. More generally, you would use this date to update some parameter of your canvas that changes during the animation.
The TimelineView itself does not return a View. It merely sets the redraw interval for whatever view is inside its closure.
In our case, we are using another specialized view called a Canvas, inside that TimelineView.
The Canvas might be familiar to you. It’s really a CGGraphicsContext in disguise. It is not technically necessary to provide a Canvas here, since we could generate the animations without a Canvas. But it will likely provide better performance for complex animations.
Inside the closure for the Canvas is where we’ll do all the work. But even so, you can see it’s only a few lines of code at this point.
First, we update the particle system. This means that we are assiging a new x and y coordinate for each particle in the system. We will see that the new coordinates are just slightly displaced from the current coordinates. They are moved along the same direction by some small amount that depends on the speed of the particle.
Second, after we calculate the new positions of all the particles, we assign the baseTransform. Think of this as recording a snapshot of all of the current positions.
Third we go through each particle and translate its position by the newly updated x and y coordinates and we draw these to the context.
Fourth we apply the changes to the context by telling it to transform in comparison to what it was originally. Transform using the original baseTransform.
That’s the functional part of the ContentView.
The code also adds two bits of Text near the bottom that provide us with a notion of how big the priority queue is, and how many times we insert a new collision event into the queue. If you follow the video closely, you’ll see that after each collision, we calculate the next collision event and insert that into the priority queue.
3. Particle.swift
Let’s look at the particle. It conforms to Hashable and Equatable. It has four important properties in the x and y coordinates, and the angle and speed.
It also has two critical functions. These calculate the time until the next wall collision.
The time is the time along the diagonal line.
And note that in our context, 0 radians or 2*pi radians is off to the right: due east.
So for example, if our particle has an angle of 0.1 radians, then it is traveling to the right and just slightly down. We already know the distance from the particle to the right wall — it is the width of the screen minus the x coordinate of the particle. So we can calculate the distance along the angular path to the right wall. This is distanceToRight / cos(angle).
And likewise we can calculate the distance along the particle’s path to the wall using variations of cosine.
The two functions calculate the time to the vertical wall and separately, the time to the horizontal wall. And whichever time is smaller is the wall we will hit next.
func timeUntilVertWallCollision() -> Double {
let width = UIScreen.main.bounds.width
let distanceToRight = width – x
let distanceToLeft = x
var hypotenuse = 0.0
let actualVelocity = self.speed
// going right:
if ( self.angle >= (1.5 * .pi) && self.angle <= (2 * .pi) ) {
// going right and up:
hypotenuse = distanceToRight / cos((2 * .pi) – self.angle)
} else if ( self.angle >= 0 && self.angle < (0.5 * .pi) ) {
// going right and down:
hypotenuse = distanceToRight / cos(self.angle)
} else if ( self.angle >= (0.5 * .pi) && self.angle <= (.pi) ) {
// going left and down:
hypotenuse = distanceToLeft / cos(.pi – self.angle)
} else if ( self.angle >= (.pi) && self.angle <= (1.5 * .pi) ) {
// going left and up:
hypotenuse = distanceToLeft / cos(self.angle – .pi)
}
let trueTime = abs(hypotenuse) / actualVelocity
return trueTime
}
4. ParticleSystem.swift
The ParticleSystem is of course where we create and update the positions of all the particles.
In the createParticle() function, we simply assign a random angle and random coordinates to each particle.
The angle is random but always between 0 and 90 degrees, so the particles all start out going down and to the right.
And the coordinates are random but in a range that starts them all near the upper left of the screen. The screen of my simulator is 1194 X 834. So starting values between 0 and 100 will all be in the upper left.
The update(date:) function is our first important function.
It goes through each of the particles in the particle system, calculates the time until each hits a wall, and inserts that time into the priority queue.
Note that the function calculates the initial priority queue once here, and after that, the calculations are done in evaluateNextWallCollision() in the PriorityQueue.swift class itself.
Particles spend most of their time moving in a straight line. Exactly how far depends on their velocity. This is calculated here:
particle.x += cos(particle.angle) * particle.speed * timeBetweenContextUpdates
particle.y += sin(particle.angle) * particle.speed * timeBetweenContextUpdates
Here is how the class creates particles and updates their positions:
// Create particles with angles and positions randomized to a small range of values
private func createParticle() -> Particle {
let angleDegrees = Double.random(in: 0…90)
let angleRadians = angleDegrees * .pi / 180
return Particle (
angle: angleRadians,
speed: 300,
xCoord: Double.random(in: 0…100),
yCoord: Double.random(in: 0…80)
)
}
func update(date: Date) {
let timeBetweenContextUpdates = date.timeIntervalSince1970 – lastContextUpdate.timeIntervalSince1970
lastContextUpdate = date
// Here’s where we add a small amount of x and y distance to the position of each particle
for particle in particles {
// Here we figure the first collision of each particle after the initial particle creation:
if !didInitialCheck {
// Here we first calculate the time until the next vertical wall collision, where
// a vertical wall is the left or right side:
let hTime = particle.timeUntilVertWallCollision()
let vTime = particle.timeUntilHorizWallCollision()
let timeToHit = (hTime < vTime) ? hTime : vTime
if timeToHit > 0 {
let updateDate = Date() + timeToHit
let particleUpdateEvent = ParticleUpdateEvent(P1: particle, P2: nil, updateTime: updateDate)
priorityQueue.insert(x: particleUpdateEvent)
}
}
particle.x += cos(particle.angle) * particle.speed * timeBetweenContextUpdates
particle.y += sin(particle.angle) * particle.speed * timeBetweenContextUpdates
}
didInitialCheck = true
// Call this on a regular interval
priorityQueue.runPriorityQueue()
}
At the end, we call runPriorityQueue. Let’s look at that next:
5. PriorityQueue.swift
The PQ array in the PriorityQueue class holds all of the particle update events. Its order is maintained in reverse chronological order.
The oldest events are at the highest index number. This is roughly a first in-first out FIFO order. But not exactly.
We call runPriorityQueue() on the TimelineView schedule.
So it may happen 60 times a second — or whatever frequency the TimelineView is scheduled to update.
public func runPriorityQueue() {
var done: Bool = false
if startingDate == nil {
startingDate = Date()
}
while !done && PQ.count > 1 {
let updateEvent = PQ[PQ.count – 1]
if updateEvent.updateTime <= Date() && updateEvent.p2 == nil {
// This is a wall event, so we will hit the wall and then reverse angle while keeping the velocity the same
if (updateEvent.p1.y > (UIScreen.main.bounds.height – 10) ) ||
(updateEvent.p1.y < 10) {
updateEvent.p1.angle = reverseAngleHWall(updateEvent.p1.angle)
} else {
updateEvent.p1.angle = reverseAngleVWall(updateEvent.p1.angle)
}
PQ = deleteMinimum(PQ)
evaluateNextWallCollision(updateEvent.p1)
} else if updateEvent.updateTime <= Date() && updateEvent.p2 != nil{
// This is a two particle collision event
updateEvent.p1.angle = reverseAngleVWall(updateEvent.p1.angle)
if let p2 = updateEvent.p2 {
p2.angle = reverseAngleVWall(p2.angle)
}
PQ = deleteMinimum(PQ)
} else {
done = true
}
}
}
// Add a new value to the Priority Queue and delete the maximum value if the size of the Priority Queue exceeds the max:
public func insert<T: Comparable>(x: T) where T: ParticleUpdateEvent {
// Insert new events at position 1, and sink them as far as needed. But this won’t be too far, because they are almost in order.
// Previously we appended new events to the same end of the array that we were reading from, and thus they had to swim much further every time.
PQ.insert(x, at: 0)
PQ = sink(PQ, 0)
insertionCount += 1
}
Each time runPriorityQueue() is called, it does two things:
First, it evaluates whether the last ParticleUpdateEvent entry in the PQ array is scheduled to take place now or before now. If so, then we must execute it.
The update event contains the time when it must be executed as well as the particle that must change course.
Second, if the update event must be executed, then the particle reverses its angle as if it hit a wall. Because, it did hit a wall.
Exactly what that new angle is depends on the incoming angle and which wall is being hit. But it’s all the same: reverse the angle.
After we have reversed the angle, that means we have executed the update event, and we can delete it from the PQ array.
That is almost everything! But one:
When we insert a new updateEvent into the priority queue, we insert it at index 0.
And immediately after that we ‘swim’ the particle into its place in the array so the array is always maintained in order. The new events at the low index positions, the old events at the high index positions.
We have to swim the update event into order each time because when a new update event is calculated, it may be a wall collision that is going to happen soon (because the wall is already close to the particle), or it may happen later (because the wall is far from the particle).
That’s it!
Next time we’ll consider the more complicated case of particles hitting each other. When that is possible, then the number of collisions rises and the importance of the priority queue becomes even greater.