I had the bright idea recently whilst avoiding work - "I should write a maze generator". Not very good timing, I know, but I did it. And I liked it. I thought I'd show people, because it's kind of cool, and I'll also walk you through it.
Here is the working example:
I'll walk you through the basics of the code. I've never really worked with generating things before, so I'm not sure of the technical name for this approach, and honestly I'm not sure that there is one. If there isn't, I'm naming it The Fail Safe, and you'll see why.
I used a cell type approach to the map - so I started off by defining a basic cell object, and made a 2D array that filled up the entire canvas with them. Every cell has 2 important attributes: isAlive and isMaze. Those are self explanatory. On default
Cell.prototype.isMaze =false;
and
Cell.prototype.isAlive =true;
The whole **algorithm** is only a few lines long, so go ahead and check it out and I'll walk through it:
var generateMaze =function(x, y) {
//Select starting point, make it into mazevar point = cells[x][y];
point.makeIntoMaze();
failsafe = [];
//Make sure our start has places to move towhile (point.hasAliveAdjacent()) {
//Gather all adjacent spotsvar adjacent = point.getAliveAdjacent();
//Select a random adjacent, make that our point and make it into a maze//the update all the cells so they can adjust accordinglyvar randomAdjacent = randomInt(0, adjacent.length -1);
point = adjacent[randomAdjacent];
point.makeIntoMaze();
updateCells();
adjacent = adjacent.splice(randomAdjacent, 1);
if (adjacent.length >0) failsafe = failsafe.concat(adjacent);
failsafe = getValidFromArray(failsafe);
if (!point.hasAliveAdjacent() && failsafe.length >0) {
point = failsafe.pop();
point.makeIntoMaze();
updateCells();
}
}
};
We start by grabbing a cell from the inputted x and y (these are just random x and y's in range), make it into a cell, and setup our failsafe variable. That's easy.
We want to continually create a maze whilst our current point has places to expand to. Hm... continually... sounds like a loop, so let's throw together a while loop. We then grab all of our alive adjacent cells (a cell is dead if has more than one maze adjacent to it), then select a random one, and make that our new point for the next iteration, that's easy. That part took all of 10 minutes setting up. The failsafe took some more thinking, although it's logical when put all together. We treat our failsafe like a stack, where basically any leftover values get thrown onto it, and when our main point can no longer continue, we pop the top value off the stack and use that instead. Easy peasy. So then we end up continually iterating until every available value is used. Sweet.
For a while I was getting problems because I hadn't updated all of the cells on the map after setting the main point to the fail safe. The problem that arose from this is that many values that shouldn't have been considered alive, were, so it made some really crappy looking mazes.
It's interesting how much people change in short periods of time. I just went and read through a bunch of my old posts, and man, did I sound pretentious (they're gone now. Don't bother looking, they are horror-full!). Here's me taking a shot at redemption:
I'm not a Game Developer. I'm aspiring, but I don't know most of what I'd like, although I've come quite a ways.
I love programming, but I am no expert. I grasp most of the important concepts of programming (although in 10 years I'm sure I'll look at the code I'm writing today and projectile vomit).
I don't know what I don't know.
There. That's my go at being humble, and trying to realize "I don't know what I don't know."
So, it's been a while. I understand that. Good thing I don't have a following, because if I did, this (inconsistent posting) would look really bad. Since you don't know me, I'll try to catch you up a bit.
I had a nice long summer, and had the honor to serve at Bear Creek Scout Reservation. There I was able to meet a lot of nice people, and learn more about myself. A lot of weirdos, crazies, and a series of insane camp stories were written into my memory (which will make some great examples later). I also enjoyed many a hours sitting on the edge of my seat finishing up my Ray-Caster I wrote in C++.
I've had some more experiences with programming, and recently was introduced to the one and only, Jacob Allred, creator of Fake Name Generator. Him and I are currently working on a new website - mainly for geeks - that generates random RPG character ideas (and eventually more!!!). I don't want to spoil it too much, but I'm really excited about it.
I recently read Game Programming Patterns by Bob Nystrom. It is extremely well written, and I recommend it to ANY PROGRAMMER REMOTELY INTERESTED IN GAMES. First off, if you're a programmer, you are more than likely interested by games. Second off, everything in that book is applicable to more than games. A great thing about it is that Nystrom has a great sense of humor, which makes it a lot easier read.
Now I've been wondering for quite a while what Bitwise operators do. Sure, I understood what their functions are, but I couldn't think of a single way to use them! They just never seemed applicable XOR useful! So I finally got down and researched it, and I figured since there is a somewhat limited resource on how and when to use Bitwise operators, I'd publish my findings here, so here goes nothing.
(Note: All example code will be in Java, but it's pretty easy to understand, so if you know any C language you should get it)
First things first, lets list what all of the operators are:
Right Shift
Shown with a '>>', and moves all bits to the right equal to the number specified on the right of the operator.
Left Shift
Shown with a '<<', and moves all bits to the left equal to the number specified on the right of the operator.
OR
Shown with a '|', also known as the Inclusive OR operator.
XOR
Shown with a '^', and also know as the Exclusive OR operator.
AND
Shown with a '&', similar to '&&' binary operator.
Unary Bitwise Complement
Shown with a '~', similar to the unary '+' or '-' operators for integer variables.
So there. Now we know what they are, and you might have some idea on what they actually do. But you might not also, so let's go a little in depth.
Bitwise Operators Explained
Right Shift
The right shift is relatively simple. Let's say you have the following code:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b101; //Which is equal to 5System.out.println(Integer.toBinaryString(num1 >>1));
}
}
--Prints--10//Which is equal to 2
The Right Shift literally shifts all the bits one to the right. But another interesting thing is, for every bit you shift to the right is basically the same as dividing it by '2'. In my example I shifted by one, in integer division it'd look like this '5 / 2 = 2'. And if we continued this with larger numbers, we could get things like '200 >> 4 = 12'.
Left Shift
Left Shift is very similar to Right Shift, but now it has a somewhat different application as opposed to division. Let's see an example first, then I'll explain:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b101; //Which is equal to 5System.out.println(Integer.toBinaryString(num1 <<2));
}
}
--Prints--10100//Which is equal to 20
If you haven't already noticed, shifting to the left is the same as multiplying the number by '2' to the power of the amount of shifts. In this example we could right it as 'num1 * (2 * 2)', and for every additional shift, we add another ' * 2' in the parentheses.
OR
Now we start getting to the more interesting operators. The OR operator compares every bit between two variables, and for every point that is either '1' and '0', or '1' and '1', evaluates to '1' on the result of the equation, for example:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b10100010; //Which is equal to 162int num2 = 0b00100100; //Which is equal to 36//10100110 (This is what should be printed)System.out.println(Integer.toBinaryString(num1 | num2));
}
}
--Prints--10100110//Which is equal to 166
Hopefully you can see that this is fairly simple, and the result is that every position that had a '1' in it somewhere resulted in a '1' in the print statement.
XOR
XOR is very similar to OR. It is known primarily as the Exclusive OR operator, and that is because it functions the same as the OR operator, except that any position that on both inputs has a '1' results in a '0' in the print statement. I will not further explain this as I feel it is simply illustrated, but here is an example using the numbers from the OR example:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b10100010; //Which is equal to 162int num2 = 0b00100100; //Which is equal to 36//10000110 (This is what should be printed)System.out.println(Integer.toBinaryString(num1 ^ num2));
}
}
--Prints--10000110//Which is equal to 134
AND
The AND is used a lot (In Bitwise terms), and is like the opposite of the OR operator. AND takes two variables, compares them, and if two positions both share a '1', then that is copied down into the resulting equation, for example:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b1010; //Which is equal to 10int num2 = 0b0110; //Which is equal to 6//0010 (This is what should be printed)System.out.println(Integer.toBinaryString(num1 & num2));
}
}
--Prints--0010//Which is equal to 2
Unary Bitwise Complement
The Bitwise Complement operator is also fairly simple. It is applied to a single variable, similar to a negative symbol (-). When it is applied, it shifts all the bits to their opposites, all '0's to '1's, and all '1's to '0's. This is the same as making the number negative, then subtracting 1, which can easily be expressed in the equation, '(n * -1) - 1'. Here is some example code:
class BitwisePractice{
publicstaticvoidmain(String[] args){
int num1 = 0b0001; //Which is equal to 1System.out.println(Integer.toBinaryString(~num1));
}
}
--Prints--11111111111111111111111111111110//Which is equal to -2
Notice that since an 'int' variable in Java is 32 bits, it prints all bits. This obviously changes from language to language.
An Example of Usage
The applications of Bitwise operators are infinite, like writing checksums, compressing files, and so on, but let's start small.
The House with 8 Doors
The environment we are going to now mirror is a House. With Eight Doors. It is our job to know which doors are open, closed, and be able to close or open any door.
So let's start small.
class House {
publicstaticbyte doorsOpen = 0b00000000;
}
Since our house just happens to have 8 doors, it can be perfectly mirrored with Java's 'byte' variable, which only has 8 bits. Each bit will be tell us which Door is open. If a bit is on, it is open, whereas if it is off, it is closed. For this example we will not be tracking which door is which, but if you wanted you could definitely create an 'Enum' or some 'static int's to represent each door.
Opening the Door
Now we want to write a method that accepts an int that represents which door we are trying to open. So let's do this step by step. Here is my method declaration:
publicstaticvoid openDoor(int doorNum){
}
The next step is to create a mask. Basically, a mask is a variable that allows us to get a single point from 'byte doorsOpen'. To create the mask we will create a 'byte mask', then assign it '1 << position'. This will create an empty 8 bit variable with a '1' at the index of the door, so then we can manipulate that single variable! The coding should look like so:
byte mask = (byte)(1<< doorNum);
Before you read on, guess how we will change the variable 'doorsOpen' to have a '1' at the masked point.
Well I hope you figured it out by now, but if you haven't, it's with an OR operator. So all you have to do is add the following:
doorsOpen = (byte)(doorsOpen | mask);
(Note: In Java you HAVE to typecast the result as a byte, because it might read it as an int, and give you an error)
Checking the Door
The next step is to create a method that returns either 'true', or 'false', depending on if the specified door is opened, or closed. I've set my method up like so:
publicstaticboolean isDoorOpen(int doorNum){
}
Now go ahead and create a mask variable, just like we did before.
The next step is to create an 'if' statement that checks if 'doorsOpen' is greater than 1 after being applied to the mask. Before you read on try to accomplish this.
The easiest way to do this is like so:
return (byte)(doorsOpen & mask) >0;
Do it yourself
The next step is to implement a method that allows you to switch the doors state. This just means that if the door is closed, open it, and if it is opened, close it. Note that closing a door is a bit more difficult, but if you can figure it out, more power to you!
Check the solution below:
This answer is actually very similar to the Opening the door, This time is just with a XOR operator, as opposed to the OR operator.
Closing the Door
The next step is probably the most difficult of all of the methods yet. Because it is. Sorry. We still create our mask like normal, but this time when we are reassigning 'doorsOpen', we have to use the 'Bitwise Complement' Operator, and a AND operator. We have to use them in conjunction because we want to only change the position specified when the method is called, and that's what this allows us to do. If we say 'doorsOpen & ~mask' then we will only be resetting the position specified, as the AND operator only let's positions stay the same if they are the same, and this also safeguards from just switching states instead of closing the door. I hope you understand. Here is the example code:
Homework?
Using the XOR operator it is possible to switch the values of two different variables. Can you figure out to do this? If so post it in the comments! And go ahead comment if there was anything wrong with all of this!
I've been being dishonest. Well, kind of, in a seriously strange sort of way, in which I didn't mean to. I originally meant for this to be a way for me to organize my ideas so that I could read them later, yet I haven't been able to accomplish even that. What I'm trying to say is, the last few posts, my first three, weren't really my thoughts. They were obtuse and unfocused, thinking more of myself, rather than sharing my own thoughts.
So I'll change. I already have, can't you tell?
-Tanis Half-Elven
“I wish it need not have happened in my time," said Frodo. "So do I," said Gandalf, "and so do all who live to see such times. But that is not for them to decide. All we have to decide is what to do with the time that is given us.” ― J.R.R. Tolkien, The Fellowship of the Ring
Time. The currency of the World. The one thing that no matter how much you try, will never have enough of. Trust me, I'm only a teenager and again and again this is proven to me. Yes, my agenda is somewhat different than most kids my age; I program, they play video games, I read an article on The History of Anti-Aliasing, and they read Divergent.
I feel as if every minute I am working on something new, like Learning about Pointers and References in C++, I am using that minute at the best of my ability, and learning new things in which I can't any other way. It is my progression. This is the way in which I grow.
But I look at other people, and they are spending their precious minutes... Collecting Dolls? Or even watching a show about people collecting dolls? I don't know. Sounds wasteful.
But other people would say the same thing about what I am doing.
Here is something that I was told in my first job as a Janitor, when I was just learning to code:
"Why even bother creating the things you are trying to create? Why waste your time? Because you are. No matter what you build, somebody else will always have a better working one, somewhere" --Coworker
True. I will give you this; it is correct to say that of what I build, there probably is a better one somewhere else, to an extent. You see, the reason I build things is because it teaches me. I wouldn't learn ANYTHING new if I never spent my time creating a Java Application that did Absolutely Nothing.
And because of that reasoning, I assume that no pursuit is a thoughtless pursuit. Yes, it may be wasteful, pointless, or not really worth it. But there is most likely a reason. Collecting dolls seems to invent some kind of new, interesting life for people, where they get TV shows about them, and if that is the case, that is awesome. I am happy for any person able to do what they love.
We as Humans only have so much time. But because of that, it doesn't mean that what others do with their time is worthless, as opposed to what I do with my time. Not everyone wants to be a programmer, or even needs to. In fact, now that I've learned some of the morals of programming, I would probably say that people should shy away from programming, unless they are absolutely sure they need to be programming, because 9/10 times, they don't.
So please go and do what you love, and do it to the best of your ability.
I like to read. A lot. But I find I'm not as good of a Writer, as I am a Reader. It's a strange trade off. Apologies, if I have written something that didn't make sense at all. I'm putting forth effort over here. Hopefully I'll be coming out with a new post ever **4?** days?
You know when you're in a mood to code? Nothing can hold you back; you just want to type your code. You start typing, with a new project in mind, and you get about... here:
class MyClass{
public static void main(String[] args){
/** * This code will... *Wait?!? What will it do? *How will I do that? Huh? What was my idea??? ... */
}
}
Because I sure do. I've done that. Who hasn't? For surely any passionate programmer has melded away hours on... Nothing? Or is this actually worthwhile?
I recently read an article about how people who become **masters** have about 10,000 hours of doing the thing that they are **masters** of. At least.
This figure doesn't worry me at all. I've been coding for about 9 months now, and I feel comfortable saying in that time I've coded at LEAST 300 hours. Yes. 300.
[EDIT: Well, this is future me talking. I'd like to rework the math real quick so you can see, and I'm about at 12 months now... hmmm. (12(months) * 30(days per month) * 2(hours per day) ) = 720, although this is probably a bit higher because of the amount of days I did not code (although I did code quite a bit), so a safe estimate is 600+ hours of programming. 9,400 to go.]
Another interesting thing I read talked about how people don't actually have to have great credentials or to have graduated MIT to make a large sum of money per year, right out of college (In programming, of course). What I've found is: Employers worry more about you're experience.
Lesson: Experience is everything. Program and Program and Program.
And on that note, here is my JavaScript game:
(Use 'space' to shoot; and the Arrow Keys to move)
Feel free to comment your highscores; Mine is 8880.
