Code Monster

[Olivie Inoue]

Anyonecan participate in the Hour of Code, including students, teachers, parents, and individuals of all ages.Tutorials are available for various age groups and skill levels, from young children to adults.

To organize an Hour of Code event, visit Tynker's Hour of Code page and explore the resources available for educators and organizers.You can find lesson plans and step-by-step guides to help you set up a successful event.

Tynker Hour of Code offers teachers and parents various resources, including a Teacher Planning Guide, lesson plans, activity guides, and community forums.These resources are designed to help educators and parents facilitate coding sessions and encourage children to learn computer science.

You can set up your student rosters with Clever, Google Accounts, or Tynker Accounts.If you use Clever, read this post to set up your classes.If you use Google Accounts, watch this quick setup video.To create Tynker Accounts for your classes, this quick video walks you through the process.

Once you set up a classroom, you can add students and assign programming puzzle game lessons through your teacher dashboard.You can import students to a single classroom, add them to multiple classrooms,manually create individual Tynker accounts, or have your students add themselves using a class code.

Your teacher dashboard is where you can access all your teacher guides, answer keys, student metrics, and certificates.You can see just how much your students are coding and even help them if they get stuck!You can print out personalized achievement certificates for each student at the end of an Hour of Code.

I was curious about how the monsters in Doom calculate how to reach the player. I'm reasonably sure that Doom doesn't use true pathfinding code, given the processing power they had to work with, and how you don't have to lay out paths in the levels.

I was watching a video that explained the basics; it finds the eight-way direction closest to the target, it moves in that direction until it hits something or runs down its move counter and then it recalculates it's direction.

The video shows it walking the length of a wall and says that it turns around when it gets to the end of the wall. How is it determining that it had reached the end of the wall? And then what does it do at that point? Is it trying to move to the other side of the wall? In the video there is a gap in the wall, and if the pinky moved forward just a little bit to try to continue following the wall it would get around the wall and be able to reach the player, but if it just recalculates the angle closest to the player then it would turn around and walk the length of the wall again. And if the wall was very short then the pinky would get stuck perpetually walking a very small obstacle unable to cross it.

I'm trying to understand how games programmed such behaviors back in the day. This was before we had modern pathfinding and nav mesh stuff; heck this doesn't even have path nodes like in UT99. I want to understand the logic they used to keep monsters from being stuck by simple obstacles.

basically, in that function the monster checks where its target is, and choosing a new direction to move out of 8 possible directions (i.e. monsters never walk by arbitrary lines, only horizontal, vertical, or diagonal movements are allowed). then the code checks if new direction doesn't require 180 degrees turn (because such turning is forbidden; but see below). if new direction doesn't require a turn, the code checks if the monster can move in that new dir (i.e. simulates a step). if movement is allowed, we're done.

if all new pathes are blocked, the monster finally tries to turn around -- this is the only case when it does 180 degree turn. that's why monsters "run away" from the player in narrow corridors -- they simply cannot turn around.

this is basically it. no complex logic or pathfinding, so-called AI is quite dumb. the illusion of more-or-less smart movement comes from map design, and from the feature of human brains to see patterts of smart behavior everywhere. ;-)

run forward a little. turn a little, if it is possible. run forward a litte. turn a little, if it is possible. keep doing that. never turn 180 degrees until there is no other directions available. add some randomness to the mix.

p.s.: if you want to see how dumb everything really is, turn on object view cheat on automap, and go to Doom2 MAP01. kill all zombies, then quickly run forward, and backward back to where you started. and then watch the imp walking down the corridor, and then unable to get out of that big room. it will wander there, unable to understand that it should go back the corridor it walked. ;-)

First of all, I noticed that if the player is just a little further forward they will manage to navigate through the long corridor all the way to reach the player, which is really what makes the AI "feel" more intelligent, because it (sort of) can navigate through the map to reach the player. If the player is south enough in the first room, then if a monster randomly shambles into the wall at the very tip of the hallway they recalculate which way to turn, and move south to face the player. But if the player is just north enough, when they hit that wall they turn north, and then they follow that wall all the way around and find their way to the first room.

I also noticed that when a monster finished following a wall it tries to find the player again, which can produce a little random walking. It will quickly find its way to the next wall and follow it. But the key element here is that it is not actually tracing the whole curved path to the player, just following one wall at a time, which is going to lead the monster to find the next wall.

I also noticed that while the monster randomly shambled around int he big room, sometimes they would bounce off a wall and then walk due east, (the exact opposite direction of the player,) and continue in that path perpetually until they hit another obstacle. They never get triggered by moveCount getting decremented again.

Three, why are monsters sometimes walking due east into perpetuity? Off hand I wonder if they are trying to follow the wall, but since that wall is at an odd angle, they try to follow it moving straight north, bump into it and change their angle, but now are moving away from the wall in a way that they can never detect that they have reached the end of this wall. But this is pure conjecture since I don't understand the first two points I mentioned.

sometimes they would bounce off a wall and then walk due east, (the exact opposite direction of the player,) and continue in that path perpetually until they hit another obstacle. They never get triggered by moveCount getting decremented again.

that is due to "no 180-degree turns" rule. the monster cannot turn around, so the code decides to not take any turns at all. there is a small random chance of slight turns, but most of the time the poor thing will just walk forward until it hits something.

this is basically the one question. the monster is never "following the wall" per se, it is just an illusion. what it really tries to do is check which turn it should take to face the player, and then it checks if it is possible to move into that direction (see also "no 180-dg turns" rule). if it is not possible to proceed in the new direction, the monster keep walking in the old direction. this creates illusion of "following the wall", as the thing tries to turn, bumps into the wall, and cancels the turn.

the only idea of monster movement is: "face the player, then walk forward". this is basically all what AI tries to do. the illusion of "smart" movement is created by "no 180-dg turn rule", and by checking if it is possible to move into the new direction. ah, and some very slight randomness. also, `A_Chase()` is not called on each tic, so the monster keeps walking for some time before re-evaluating its path.

also, as you can see from our experiments, another key thing to make everything work is constant player movement. if the player is standing still, monsters will (mostly) aimlessly repeat their wander actions.

and note that "no 180-dg turns rule" helps monsters to get away from narrow corridors. without that rule, monsters will be oscillating there, but with that rule active, they are forced to walk the whole corridor before trying to change their direction.

Honestly I'm pretty impressed; the one designation of not allowing them to choose a direction opposite of their current movement is such a tiny little thing, and yet it enables them to follow corridors. How did anyone think that up? Or was it just some sort of happy accident...

This is more about the specific code than the general process, but I'm wondering how they determine "second best option," or rather, how they determine that with optimal code. I can't think of how to do that without running a massive series of if statements that check all eight directions.

I think I found the code that does this in P_NewChaseDir. I see it creates an array just called "d" (which it gives an array length of 3 but only uses the second two?) and it sets one to be either north or south and one to be either east or west. (I'm guessing a quick check of player position being greater or smaller in X and Y?) But I don't understand the logic of what it is doing; how it is quickly determining each possible route to the player and whether or not it is viable.

"trying movement" is easy: the code simply calculates new coordinates in the given direction, and checks if that place is not occupied by anything. i.e. it simply simulates a "step", using the usual Doom movement logic.

3a8082e126