Did you know they used some pretty awesome techniques to code Pokémon Snap?
I absolutely loved playing Pokémon Snap for the Nintendo 64 when I was a kid. Whether it was trying to get the best score or just see how many Pokémon I can whack with an apple, I sunk way too many hours into it. Fast forward to 2021, we've got a new game coming out, and the first thing I thought when playing was "How did they program this?" Computer vision is definitely capable of pretty amazing things, but I kind of doubt the developers made a huge machine learning model to search for so many different Pokémon, recognize what pose they're in, recognize other Pokémon in the frame, etc. And even if that were the case, there's zero chance that's how they did it back in 1999. There has to be an easier way... but how?
Disclaimer: I didn't develop either the old Pokémon Snap or the new one, so I clearly don't know the exact techniques they used. However, I think I've got a pretty good theory as to how they did it. Give it a read and let me know if you agree or think I'm wildly off base.
So there are a few questions we need to answer here:
How are the Pokémon programmatically represented?
How does the Professor know which Pokémon are in the picture?
How are the other criteria (size, pose, direction, position) determined?
With those questions listed, I think we can get a pretty good idea of how the game [probably] works.
How are the Pokémon programmatically represented?
So we know this game is a 3D game, so clearly the Pokémon needs to know its position in this 3D space. I assume it also has variables for what direction it's currently facing, as well as what "state" it's in. I'm guessing each Pokémon has a list of states that correspond to different poses and a state machine for when to transition between the states (e.g. In "Idle" state, player hits it with apple, enters "Shocked" state). This doesn't sound all that impressive, but it's how I think these variables are used that get interesting.
How does the Professor know which Pokémon are in the picture?
I believe that when you take a photo, the game first takes a screenshot (which should just be as simple as reading the frame buffer and dumping it to an image), then determines the score of your picture right then and there. You heard me right; the game already knows how terrible your picture is the second you take it; the Professor is just the messenger. And how does it do this? Ray casting.
Ray casting is essentially where the game "casts" a line from the player straight out into the horizon and computes if it hits an object in its path. So in the picture above, you draw a line from the player's eye and the computation can determine that there's a circle blocking a few of those lines. I believe this is the exact same technique used in Pokémon Snap. The game draws a number of lines from the camera and checks if any of them hit any Pokémon. And if it knows which Pokémon it hit, it can know all of those variables pertaining to that Pokémon, including its pose, direction, etc. It should also know if it hit any other Pokémon in the same shot, so that's how that "Other Pokémon" category is calculated.
How are the other criteria (pose, size, direction, position) determined?
Once we know what Pokémon are in the picture, we can start reading through its variables. Pose can be read from the Pokémon's state, then have some lookup table for how many points that state is worth. Size can be determined by how far along the ray the Pokémon is - the closer along the ray means a larger Pokémon. Direction can be calculated as the difference between the player's direction and the Pokémon's direction - it's directly facing the Player if the Pokémon's direction differs 180° from the player, and any distance from 180° can be subtracted from the maximum points. Position can be determined by the Pokémon's position in the 3D space minus where the centermost ray "intersects" with the plane the Pokémon is on - the Pokémon is in the center of the photo if the Pokémon is 0 distance units from the centermost ray, and any distance can be subtracted from the maximum points.
And there you have it! I found a comment on a Reddit thread about someone who developed their own Pokémon Snap inspired game and they used the exact techniques I've described here, so I hope there's some merit to them. What do you think? Do you think I nailed it or do you think they secretly had super advanced computer vision algorithms back in the 90s?
Hey, so uhh I kinda fell off of Apptober. This whole pandemic is a huge blow to motivation for a lot of people, myself included. I’ve been on work-from-home orders since March 2020 and have orders to do so until at least June 2021. I’m happy to stay home for the safety of others, but I am also a very extroverted person and not having that social component has been very difficult. As a result, I’ve been struggling with a lot of things and motivation to do a coding project was part of that.
With that out of the way, I wanted to share something cool I wrote. Halloween is coming up and I wanted to do something that would allow the kids that are still gonna go trick-or-treating to get the candy they want but be safe with regards to the pandemic. My plan was to package a few pieces of candy in a little baggy and have the baggies spread out so the kids could just come up and grab one. No need to worry about digging through a bucket of candy every other kid has put their hands in.
So I went out and bought two of the big bags of variety candy. I guess I kind of expected those bags to be pretty uniformly distributed, but I was wrong. One bag had 100 Snickers and only 18 Starburst. I had 50 bags and about 350 pieces of candy. The challenge was spreading the candy out evenly in a way that no bag gets too little candy, too much candy, or too many/few of one type of candy.
So why is this on a coding blog? Well, this right here is an optimization problem. Is it weird that I made an optimization problem out of Halloween? Probably. But the problem existed nonetheless and I needed a solution. I threw together a model, which looks like this:
Basically, I wanted to ensure the following: each piece of candy is used, each bag has about the same amount of candy, and each piece of a specific candy must be used. I wrote a simple program in C++ using the Gurobi Optimizer because I didn’t feel like writing my own linear programming solver. If you want to see the program, I uploaded the code here: https://pastebin.com/YFzsvQKp . The results of the program was this:
I was able to follow along and pack all 50 bags with every piece of candy. It was so beautiful getting down to the last bag and the program had perfectly spread out every piece of candy. The bags of candy came out like this!
So I thought that was cool. Only 150 lines of code (minus the thousands of lines in the optimization library) was able to do this! I went ahead and sealed the bags and quarantined them off so that I can grab them with gloves on Halloween. I just hope kids come (safely) so I don’t have to eat all of these!
I went ahead and started a page that will be the “main” item being developed this Apptober. I still don’t know what games I want to do, but I figured a hub of sorts that links to games while also giving out some cool info about the games and theory behind them would be pretty neat. So if you want to find out more about Game Theory, check out my new page: https://daswick.github.io/Game-Theory/. I’ll be updating this pretty consistently as I learn more, so it’s pretty empty (and ugly) as of now, but I’ve got one section up about the most infamous dilemma in game theory that I’m sure you’ll find pretty interesting!
And I was able to find a game of Tic-Tac-Toe that I had developed while investigating game theory. It turns out that with a fairly simple program, you can make an “AI” that mathematically will never lose a game of Tic-Tac-Toe. Don’t believe me? Go ahead, try it: https://daswick.github.io/Game-Theory/games/TicTacToe.html. If you can win the game with screenshots as proof, I will personally recommend you to the council of the smartest people to have ever lived. Just don’t be discouraged if you can only tie it ;)
Man, this year really just came and went. I honestly didn’t even know it was October until I got tagged for Apptober. It’s also weird to think how far I’ve come since I started doing Apptober. My first Apptober experience was when I was just a junior in undergrad. Now I’m an embedded software engineer with a year with my company under my belt. Time really does fly when you spend every waking hour staring at a computer.
One thing that hasn’t changed since I started with Apptober is that I always want to learn more. My first year had me learning about user interfaces in C# (which can I just say has not helped me at all now that I work on embedded stuff where the only interface is a terminal?). My second year was learning about synchronization and neural networks. And my third year was learning about... elevator algorithms (hey, it sounded fun). This year is going to be no different.
As of lately, I’ve been really interested in the field of artificial intelligence. I just think it’s neat that you can write programs that can schedule all the games of a sport, beat world champions in chess, and read and translate text just from a blurry picture. And it does all of that based on just an insane amount of math. I was kind of contemplating going for a higher degree studying artificial intelligence, but I think I just want to study it casually (I want to learn about it but I think I would hate a career doing it - if that makes sense).
One piece of AI that has really piqued my interest is Game Theory (No, not the MatPat series). It turns out that there’s an entire field of mathematics based on how to formulate interactions as games and how to pick optimal strategies. This could mean games like Tic-Tac-Toe or this could mean nuclear plant management. I’ve been meaning to study it but never could fully start, so this is as good a time as any to push myself to learn it.
So what am I going to code? Well there’s a number of “games” that can be taken from game theory. Any game from Rock Paper Scissors to Backgammon can be strategized using game theory. Honestly, I don’t know what games I’ll code, but there will definitely be games (that you guys can play!) and there will definitely be math (that will bore you guys!). So let’s go learn some theory, some GAME THEORY! Thanks for reading!
Also go check out @apptober to see what the others are doing. There’s a lot of really smart people doing really cool things, so please give your support!
As it turns out, a “perfect” algorithm for delegating the floors to the elevators is impossible. I created a simulation that emulated the elevators to determine what ordering would be create the best times. What I found was very similar to how other scheduling algorithms (such as CPU scheduling) have no perfect solution, since a perfect solution would require knowledge of the future.
Take for example, we have two elevators, one that starts on floor 2 and the other on floor 3. We want the elevators to go to floors 5, 6, 7, and 8. If it takes two seconds to change floors and five seconds per destination, then the optimal solution would be for elevator 1 to go to floors 5 and 6 and for elevator 2 to go to floors 7 and 8. However, if 5 or 6 came in to the input queue first, the logical thing to do would be to assign it to elevator 2 since it is closer by one floor.
This is the problem. If, in our example, we knew about all four destinations, then it might be possible to spread them out perfectly. However, we react to every destination when we get it. Therefore, we can only try to get as close as we can. I changed my algorithm to be a little smarter. Rather than assigning the floor to the elevator that was the closest, I also took into consideration the number of destinations that elevator had. So if one elevator was slightly closer to a floor than another, but it had a few destinations while the other had none, it would be wiser for the other elevator to be sent.
This is the simulation that I ran. It gave the top three solutions for the inputs given, as well as three relatively bad solutions, and finally mine. You’ll notice each solution gives a max duration, a total duration, and an average duration. I measured these by the max duration, which is the longest any elevator took in that solution. My solution was a few seconds behind the best and a few seconds ahead of the worst. It’s definitely an improvement of what I had before, so I’ll take it.
I also commented my codebase, so feel free to take a look. These changes were made in this pull request.
I got a little carried away today, but that’s okay! First, I started off looking into typical elevator scheduling algorithms, and it turns out most elevators just use a simple disk-scheduling algorithm called LOOK. LOOK basically entails that an elevator will start going in a direction and satisfy any requests that lie between the floor it started on and the requested floor closest to the limit (such as the ground floor or top floor). It can then turn around and satisfy the requests in the opposite direction. I’ve implemented a fairly simple version of this that gets the job done, though I think there’s some optimization to be made. You can read more about the LOOK algorithm here. It’s very similar to the SCAN algorithm, seen here, though the only difference is that SCAN goes to the very end before turning around while LOOK goes to the furthest requested destination.
Secondly, I wanted to see what my memory throughput was like. I installed Valgrind and found I was leaking a few bytes, namely with my EventHandler. I went ahead and made those shared pointers, so that once they went out of scope, they were automatically freed. I also found out the virtual machine I was using has just about enough memory to run Eclipse and my program, so a few malloc problems arose when there wasn’t enough RAM. Good to know I spent half an hour thinking I was having some serious memory leak issues.
Finally, I also added a “door opening/closing” sequence. Now when an elevator reaches one of its destinations, it “opens its door”, waits for five seconds, and “closes its door”. If only I could also have it play some jazzy elevator music, then the experience would be truly authentic. Below is a demo demonstrating this “door” sequence.
If you want to see these changes, they’re in this pull request. I think sometime soon I’m going to go through and comment a lot of the code to make it easier to understand the logic. I may also be planning on a display system for all of this, though I need to get a way to record my screen for that. But for now, I’ve said too much.
Now that I’ve spent the first half of Apptober getting the foundation into place, the bulk of the work is in the algorithm. I’ve started by just seeing which elevator is closest to the requested floor and sending that one. Below is a demo where between an elevator on floor 3 and one on floor 5, when a request for floor 7 is added, the elevator on floor 5 is sent out. Next should be checking the direction.
I decided that for the halfway mark, I would “clean” the program. I’ve been trying to create a Makefile for the program since I started, but I never understood what was happening. I finally hashed it out and (with the generous article at https://www.partow.net/programming/makefile/index.html ) I was able to create this. I modified the given one to suit my needs, and this is what I came up with:
It took me a good few hours to even understand what was happening, but I’m pretty happy with the results. If you want to see everything I cleaned up, the changes are in this pull request.
Got a good amount done this weekend. I was able to have the elevator handle whenever it receives a signal for adding a destination by using the CoreTimer and EventHandler classes we developed earlier. I don’t know if words will do it justice, so just check out this demo:
It starts with the elevators sending their current floor numbers to the controller for record keeping. One second in, we can pretend that the buttons were pressed on floors 6 and 7, so this information was sent to elevator number 0. Every 2 seconds, it moves up one floor. When it hits floor 6, one of its destinations, it signals that it reached a destination. Then at floor 7, it hit its last destination, so we convey that the floor changed, a destination was reached, and the direction changed to 0 (no direction) to indicate it is ready.
I decided to work a bit more on fleshing out handling sending and receiving signals between components. I added (or rather started using) a listener interface to “publish” the signals between threads. Plus, once a signal is received, it is parsed and an event is sent based on the signal.
For example, here is a demo where the controller sends a message to elevator 0 that it should go to floor 8. The controller sends this signal, and asynchronously the elevator receives the signal, then published an AddDestinationEvent, which is then received by the main elevator class. Through this chain, the controller class (in its own thread) told one of the elevators (in its own thread) to go to a specific floor. This is the type of separated behavior I was hoping to emulate, since it’s very likely that in actual elevators, the program for the “controller” and the program for the “elevator” aren’t even happening in the same processor.
As always, these changes were made in this pull request.
Short post today. I wanted to centralize some of the signal sending and receiving code within the components, so I added a class to the Elevator component to do just that. I also mapped out the signals to values to use. That mapping is as such:
The values are the way they are such that each “signal” only has one bit set to 1 (i.e. floor button pressed is represented as 0b01000000 while controller add destination is 0b00010000). This made room for eight different signals, which is nowhere near enough for larger embedded systems, but should be enough for this simulation. I did leave some reserved for now in case some more come up.
And here’s an example of the elevator components sending their current floor status to the controller. Pull request here.
As much as I love C++, there are some areas that make little to no sense.
I say that because today, I introduced a method for sending messages between threads/processes. A subject in operating systems I did poorly with is interprocess communication, which is exactly what this is. I opted to use the message queue from C, and man it was not friendly. I spent a solid 15 minutes trying to figure out why it was crashing about some invalid pointer issue. I even got as desperate as to use gdb’s backtrace, which pointed me to something idiotic.
So to use the message queue, I pass in a struct that I created. I defined it, I named it, and I thought I got to choose what went inside, as long as it had a long in it. I saw the documentation had used a character array alongside the long with the text “You can put whatever you want in there as long as there’s the long”. I took this as “As long as that struct has a long in it, you can put whatever you want in the struct.” What it actually meant was you can put whatever you want in the character array.
Anyway, now that I wasted half an hour of my life on that, here’s a demo:
This demonstrated that the Controller class was able to send a signal (albeit just the word test) over to the Elevator class. I’ll be refining a lot of this later, I just wanted to get something up since I didn’t post yesterday. And as always, changes seen in this pull request.
As much as I want to start development on the actual logic, I knew I needed more common libraries for this to function. This day’s library was an event handler!
What I’m thinking is going to happen is that an elevator is going to get a signal (that’s an upcoming library) to indicate someone requested the elevator on a specific floor. This will then publish an event so that any class within the Elevator component can know a floor request event is happening. From what I’ve seen, this is fairly typical in embedded systems to alert other parts of a component when it received a signal.
Here’s a small demo of the elevators adding and removing themselves as event listeners, as well as a “floor request” event being published to elevator 0. It doesn’t do anything with it yet, but what it does will be the focus of a good day or two of algorithm design.
This EventHandler class was created in this pull request.
I got a good amount of work done today! I designed and implemented two more common components: one for timer events and one for thread-safe printing.
Both of these components have detached threads that run on loops. I could have implemented it in a way where the loops only wake up through signals or other low-level concepts, but I opted to just have little microsleeps between each event. For example, if a timer were to run for two seconds, it would sleep for 100 milliseconds until the time elapsed exceeded two seconds. I chose to do it this way for simplicity and ease of developing. I also had to figure out how singletons work to ensure the printing was truly thread-safe.
I created a little demo where the elevators wake up and go up a floor every two seconds. I ran this demo twice and you can see the elevators go from floors 2 and 5 to 6 and 9 respectively. The timestamps also exemplify the timer in action.
The timer was created in this pull request and the printer in this pull request.
Hello! I took yesterday off as I needed a bit of a mental health day, but I’m back at it today.
I started to write some logic for the elevator class, but I quickly realized an issue: if the “elevator” reaches a floor and then the program turns off, when it turns back on, the floor will have been reset. So instead of continuing to work on the elevator class like I probably should have, I wrote a common component called Persistence. Typically with embedded programs, there’s some flash memory on the hardware that any data can be read/written to in some fashion. Since I’m just emulating an embedded system, I just opted to have text files in a folder. I may look into other ways, but that was the quickest dirtiest way to do it. Now, the elevator will remember what floor it was on when it boots back up. This is evident by this little demo I made:
For now, the only “data” being persisted is the floor numbers, but I may persist more throughout the components. This was done in this pull request, and you can see everything including the new changes in the repo.
Starting to get back into the groove of things, I’m trying to figure out how to post updates. I’m not used to posts that aren’t inherently educational, so this is pretty new.
Anyway, I did a bit of restructuring, now having a class for the actual simulation so the main file only needs to call a few things. Having the class, appropriately named ElevatorSimulator, also allows me to manage the components more effectively. I also did a bit of research on interprocess communication, namely message queues. I think I have a good basic implementation I would be using later on.
The files changed as well as the results of running the program is seen below:
You can also track the changes in this pull request.
Hello everyone! Long time no post. Last time I participated in Apptober, I was a student. Since then, I’ve gone and graduated and got a job as an embedded software engineer developing applications for vehicle hardware. Because of this, my interest in embedded development has been piqued.
Background:
One system that has always made me wonder how it was developed was elevators. How they all can communicate with each other and figure out which unit to send when someone requests an elevator is a mystery to me. So I want to figure it out and simulate an elevator system!
Objectives:
Theoretically, it wouldn’t be too hard to have all of this happen when everything is in the same thread. That’s why I’m going to try and separate everything as far as I can to simulate the code being run on different control units. Now, I don’t have multiple computers nor do I have the patience to set up multiple virtual systems, so I will just be creating different processes for each unit. This creates the challenge of how the different units communicate with each other, which I will need to revisit my operating systems notes.
Also, apparently elevator algorithms are actually somewhat complicated. I figured it wouldn’t be the easiest thing to determine which elevator to send when someone requests a floor, but it’s apparently an operating systems problem. I’ll investigate different algorithms for this and implement the best one.
Requirements:
At the end of Apptober, I’d like to have a system that simulates an elevator system. The number of elevators, floors, etc. is yet to be determined, but reasonable values will be used. The development will be done in C++ on a Linux environment (for now, I have a virtual machine running, but I may switch to my older Ubuntu laptop). I won’t promise I’ll post every day like I have in the previous years. I want to work on this and hopefully get it done during Apptober, but the stress of daily posting can get a bit much.
And you can track my progress! I’ve decided to post my code on GitHub for anyone to view. I’m fairly familiar with Git, so this is just more practice. You can view the GitHub here: https://github.com/daswick/Elevator-Simulator. I’ve already made a few commits getting a general framework outlined.
And of course, check out the other participants of Apptober! The hub is over at @apptober, go give them some love.
