I Coded Pacman but it's Procedurally Generated

hello everybody after years of making many and i mean many arcade games there was always one game that i've always wanted to make and it's a game that is perhaps most synonymous with the term arcade game and that is of course pac-man for some reason something always held me back from making it but i realized something about pac-man it's a great game and all but since the map is the same every time you play it it gets kind of boring after a while what if instead every time you played you experienced a brand new map that nobody has ever played before much like a new world in minecraft now it would be foolish to just try to code the procedural generation right off the bat so i figured i should just start with making standard pac-man first and so i got to work the first thing i did is that i made a grid to represent the map using this block of tiles now it looks a bit strange right now but after i filled in the grid with the standard pac-man map it starts to resemble the pac-man we all know and love but the textures don't connect so what do we do well a few years ago i worked on a small 2d terraria style game and the same problem arised with the tiles the way i solved this problem was with a 4-bit number and some bit-wise operations don't worry i promise it's interesting let's take a dirt tile for my game as an example if you looked at the tile sheet in the game you would see a strange arrangement of 16 different textures of the dirt all corresponding to different tile connections but the order isn't random if a tile is on its own we will pretend that it has a value of zero and each side of the tile will represent a different bit the top one will be one and each side going clockwise will be one bit value bigger if the tile was above we would turn on the one bit and our texture number would be one which corresponds to the top connected texture in my tile sheet if the side was connected it would be two and the second index in the tile sheet is the correct texture if we had multiple sides at once then the numbers are combined through an operation known as a bitwise war if i take two numbers in binary and check bit by bit if either bit is on and store that as a result then that is the bitwise or operation so if i take the numbers one and two representing the top and right sides of the tile and combine them together then we get the number three and the third index of the tile sheet is the correct texture it turns out that any combination of these four sides can be described using a simple index in a texture sheet now applying this to pac-man was surprisingly simple after designing a set of tiles to use i gave each tile and the grid a face variable to describe this index then i have a function that gets called after the grid is created to check if a tile has any solid neighbors and if so then the index gets updated using the bitwise or and presto all right it works now and i decided to add dots as well by simply making another tile state and rendering a separate texture now i know exactly what some of you are going to say um noodles don't you know that your textures don't look exactly like the original pac-man textures yes i am perfectly aware but this is my pac-man so i'm gonna do what i want plus my system is a lot better for procedural generation as we will see later anyways the next thing i did was to make a box to represent pac-man and let's see if the collision works hold up wait a minute well it didn't work mostly because i forgot to even use the collision to begin with but now it finally works so now that i have a box it was time for some animations to implement this i created a separate sheet for sprites instead of tiles and i created pac-man on all of the ghosts as well while i was at it now just like the tile sheet i can isolate a specific part of the texture for rendering and create animations using it so let's see if pac-man is animated correctly [Music] all right there we go and i can now eat pellets as well since the pellets are part of the map when pac-man is on top of a pellet then the tile gets changed to an empty tile so now that we have pac-man it's time to add some ghosts now out of all of the parts of this process adding ghosts was by far the most difficult i ended up coding what is known as a breath first search algorithm that generates a path to a target by searching all nearby tiles using what is known as a frontier and if it reaches its target it works backwards to generate a path to the start i'll leave this amazing website in the description below if you're curious about implementations but i'm really happy with my implementation that i ended up coming up with so let's see if it works [Music] ah yes it works wait did it just freeze all jokes aside i now have the pathfinding working and it's time to talk about the ghost's behavior each ghost could be in one of three different states the first state is called chase chase is when a ghost is actively seeking out pac-man and will kill pac-man unless a ghost enters the scatter state when a ghost scatters it picks a random tile to move towards giving pac-man a chance to get away and the last state is known as the frightened state it is exactly the same as scatter except that the ghosts move slower this is after pac-man eats a super dot and these all come together to create the ghost behavior and with this normal pac-man was almost done except for the ui i made a simple ui to keep track of the score and the lives and we now have a working pac-man clone so it's time to start the procedural generation to make the generation more interesting i thought that i would start by making the pacman grid a bit bigger so i tested to see if my code adapted correctly to being scaled down and somehow it did the next test was to make sure that my pathfinding algorithm for the ghosts was robust so i filled the normal grid with noise and it held up perfectly now for this procedural generation i need to have some consistency between all of the grids so i decided that in the dead center of every grid there would be a ghost spawning box but making even that had some strange bugs [Music] but after fixing all of that i now have a base grid that i could work with so here's the plan starting from the center box i want to generate what are known as branches the branches will essentially trace a path for pac-man to be able to travel on so after writing this very strange-looking function to generate a starting point for each branch i now have this now with these branches i want them to act as an eraser and trace paths throughout the grid so i added code to allow them to move forward [Music] once i add multiple back though they occasionally generate right next to each other creating this ugly clump of dots so i added a check to ensure that no two branches are right next to each other the next thing i did was to make it so that the branches could turn so if they hit a wall they have to turn now it is starting to look like something since there are still these large chunks of tiles and no real turns i decided to create what i call sub-branches sub-branches are randomly generated as a normal branch moves but are perpendicular to the main branch they are also smaller but can turn like the main branches can so how does it look well i mean there is more space but it doesn't look the best okay it looks like there is hope though one of the big problems are these branches that just create dead ends everywhere since i made it so that the branches have a set size once they reach the end they just stop this is important though to stop the grid from becoming entirely dots so i'll keep the length limit but if it reaches the limit and is still tracing a solid set of tiles it will continue forward until it reaches the end and now we are finally getting somewhere now i still have to add super dots the problem is is that some grids generate fairly small and others larger so i'll keep track of how many dots there are and then divide the total and place a super dot evenly around the grid and with this in a little tweaking from the generation i now have a nearly perfect procedural generation algorithm since i want to be able to generate a grid to mess around with while also being able to replay grids that i like it was time to implement a seed system now i don't program correctly by modern c plus standards i've just been using the function rand this whole time to generate random numbers and anyone who uses c or c plus knows rand is horrible at its job but it's really easy to use and it gets the job done so i will continue to use it for fun programs like this there is a function to set a seed for rand called srand so every time i generate a grid a corresponding seed will generate as well and i decided to make a menu to display all of this information what's nice about it is i could press f2 and i could just generate a brand new grid but if i find a grid that i really like i can type in a seed and bam there it is now with everything complete let's see how high of a score i could get with a random seed [Music] no no no no well mortal of the story is that i suck at pac-man anyways i really hope you guys enjoyed this video this was definitely a fun project to work on now i can't just release this for obvious reasons but i will leave the code on github if you're curious i also just want to take a moment to thank you guys for your awesome support it really does mean the world to me and it lets me keep making more silly projects like this so subscribe anyways thanks for watching and as always i will see you in the next video bye [Music] you

Channel: CodeNoodles

Views: 87,555

Keywords: Procedural generation, Pacman, Programming, Comedy, Educational, Coding, Sfml, Code, Procedurally Generated, game development, Game design, Procedural generation games

Id: ZXnK0vlSJV8

Length: 11min 0sec (660 seconds)

Published: Fri Aug 05 2022

Reddit Comments

[u/AutoModerator]

Discord for Content Creators https://discord.gg/Pp7jerZDfh

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.