In my last article, I posted a few solutions that came to mind when trying to correct the per pixel enemy collision in order to prevent the extremely jerk movement of an enemy sprite. I didn’t write up the second solution because that requires quite a lot of room and I didn’t want the article to go on too much more.
The second solution reads like this:
2) Move the enemy away from the obstacle more and then make a random decision to it’s next movement.
The enemy is working on a pixel-based based numbering system (0 to 240 in the X-Axis and 0 to 160 in the Y-Axis), the obstacle tiles are in the character-based numbering system (0 to 15 in the X-Axis and 0 to 9 in the Y-Axis). When we choose a random direction, if the random number is parallel to the obstacle, we make another random decision (see the first description). If we move perpendicular to the obstacle we move just enough away from the obstacle until it’s all clear and then the enemy hunts down the player. The player can fool the enemy by moving just far enough to where the enemy collides with either the same obstacle or another obstacle. The solution is to move the enemy far enough away from the obstacle to where the enemy sprite will not be caught and then make a random decision. Since the tiles are 16 pixels wide and tall, let’s move the enemy backward and then make a random decision.
Let’s think how this should happen. While not being blocked by anything, an enemy sprite makes its way toward the player. However, once there is an obstacle in the way, we need to try to find another path, not using the time-consuming method of path-finding. What we did prior to this is roll a random number to determine a direction that was not touching an obstacle. The problem became that if the direction was parallel to the obstacle, we had to roll another random number until we finally moved away from the obstacle far enough to kick in the first case.
We also tried applying a bias to the random number so that we could make a better decision with the aim of the enemy.
Now our approach will be, once the enemy touches an obstacle, we will back away in the direction we came from for a certain number of steps, then make another random decision to travel before trying to pursue the player.
In order for this to happen, we will need 3 specific bits of information that kick in at the correct time.
Once an obstacle is touched, we need to store the direction of travel. We will need a counter to step backward. Once we have stepped backward enough, make a random decision on which way to travel. Finally, we need a flag to throw to tell the enemy to pursue the player once more, until the next obstacle is touched.
In order to store not only the steps needed but the direction of the last traveling direction, we also should know if the enemy is advancing toward the player or retreating from an obstacle. So, that’s 3 bits of information that we need to store somewhere.
Each sprite is described using 4 variables the X position, the Y position, the sprite image and finally the f (which I believe stands for function).
sprites[i].x = enemyX; sprites[i].y = enemyY; sprites[i].n = enemyImage; sprites[i].f = enemyF;
If we are clever, we can use use the .f to store several bits of information using binary.
We’ll need to know the direction and the number of steps it should take in the opposite direction.
So, right now, I’m thinking we should move back 16 pixels and then make another decision. We could also move back 8 pixels and do the same thing, but for now, let’s try 16 pixels. We’re going to have to use the .f variable that comes in FASE and it’s quite handy. So in order to use that, we are going to place bits in the variable and strip out the various bit to store and use the information.
First 4 bits should be number of steps
This is processed by stripping out the leftmost 4 bits by shifting left 4 bits using >> 4
0000 0000 = 0 steps = 0
0000 0001 = 1 steps = 1
0000 0010 = 2 steps = 2
0000 0011 = 3 steps = 3
0000 0100 = 4 steps = 4
0000 0101 = 5 steps = 5
0000 0110 = 6 steps = 6
0000 0111 = 7 steps = 7
0000 1000 = 8 steps = 8
0000 1001 = 9 steps = 9
0000 1010 = 10 steps = 10
0000 1011 = 11 steps = 11
0000 1100 = 12 steps = 12
0000 1101 = 13 steps = 13
0000 1110 = 14 steps = 14
0000 1111 = 15 steps = 15
The next 3 bits should be direction
This is processed by stripping out the leftmost 1 bits by shifting left 1 bit using >> 1, followed by
shifting right 5 bits 7.
Don’t forget to comment heavily in your code, especially when using a technique like this.
Here’s our code dump.
To call our routine (remains the same as last time).
enemyX = sprites[i].x; enemyY = sprites[i].y; enemyImage = sprites[i].n; enemyF = sprites[i].f; enemyCollision(playerXpos, playerYpos, enemyX, enemyY, enemyF); sprites[i].x = enemyX; sprites[i].y = enemyY; sprites[i].n = enemyImage; sprites[i].f = enemyF;
In our function, we are going to declare some variables and comment them.
unsigned char enemySteps; // move the enemy X number of steps perpendicular from the obstacle unsigned char enemyDirection; // which direction our enemy should move to retreat from an obstacle unsigned char enemyRetreat; // 1 = retreat from obstacle // 0 = advance toward player
Now, we need to create our bit-shifting commands. Here’s the command sequence for the number of steps an enemy should take.
// in order to split the first 4 bits from the last 4 bits, we need // some bit shifting tweaking //push the last 4 bits off of the 8 bit binary //so that 0000 0001 becomes 0001 0000 enemySteps = enemyFF << 4;//shift left 4 places //push back the bits 4 places to have the original 4 bits //with the last 4 bits now gone // which should now look like 0000 0001 again //shift right 4 spaces enemySteps = enemySteps >> 4;
Here’s the command sequence for striping out the enemy direction.
// perform bitshifting to determine which direction the enemy // should be facing // we need to strip off the left most bit by shifting once to the left. enemyDirection = enemyFF << 1; //now that everything is shifted left once //we now need to strip off the right most 5 bits //by shifting right 5 spaces enemyDirection = enemyDirection >> 5; //0000 0000 = 0 = north //0001 0000 = 1 = south //0010 0000 = 2 = east //0011 0000 = 3 = west //0100 0000 = 4 = northeast //0101 0000 = 5 = northwest //0110 0000 = 6 = southeast //0111 0000 = 7 = southwest
And here’s the code for stripping out the state of the enemy, either advancing or retreating.
//The final bit of information is if the enemy //is advancing toward the player for retreating from //an obstacle //This is stored in the leftmost bit //retrieve by bit shifting 7 bit to the right enemyRetreat = enemyFF >> 7; //1000 0000 = retreating from obstacle //0000 0000 = advance toward player
Of course, this information is needed in the function and we will get to using the information a little later in this article, we need to concern ourselves with placing this information back into the variable. This function is called once per enemy per game loop, so this will be called every time we move an enemy sprite.
This can be done by reversing some of our steps and then using the bitwise OR operator to recombine them. It’s rather simple to place in your program.
So let’s look at our steps.
Since we’re not having to strip out bits like we did when we took the variable into our function, The operation is a little more straight-forward than the initial steps.
The enemySteps variable is already in it’s proper place, as we are counting from 0 to 15, so we don’t have to do any shifting with that variable.
The enemyDirection needs to be shifted left 4 bits to push the bits from bits 1 to 3 to the bits 5 to 7. This can be done by using << 4.
from 00000111 to 01110000
Finally, the enemyRetreat variable needs to be shifted over 7 bits to push from bit 1 to bit 8. This can be done by using << 7.
from 00000001 to 10000000
Our final step would be combining the bits using the bitwise OR operator
As with the prior routine, we need to make sure we comment, so that we can, later on, tell what in the world we were doing in the first place.
Here’s our code.
//take the 3 variables //enemySteps, enemyDirection and enemyRetreat and shift back to their proper spot // enemySteps should already be in it's proper place // enemyDirection needs to be shifted left 4 bits enemyDirection = enemyDirection << 4; //enemyRetreat needs to be shifted left 7 bits enemyRetreat = enemyRetreat << 7; //enemyF now has our 3 variables stored and is returned back to main loop enemyF = enemySteps | enemyDirection | enemyRetreat;
We can take in the new variables and can return the variables back to the main loop. We just need to figure out what we are going to do for the enemy AI.
Now, we need to lay out logically how each enemy should proceed once they touch an obstacle as we need to determine which action will not only move them away from the obstacle. In some cases this will be rather easy, just move perpendicular to the object. Other cases will not be quite as easy, such as when the enemy comes on a series of objects. The best way to determine this is by graphing each case.
Let’s start out with the simplest cases first, here we will show the enemy in red and the player in green.
No barriers. Case 0
Action: Move toward the player either vertically or horizontally. Make a random decision 50/50 to decide on a direction toward the player and move toward the player 16 pixels. This will be important a little later on.
Barriers on 3 sides. Cases 7, 11, 13, 14
Action: move backwards 16 pixel steps away from barrier, only going to show the first case.
Barriers on 2 sides, north and south, Case 3 or east and west, case 12
Here, we actually have a few choices to make. In the cases shown above, we would just move toward the player, in the horizontal or vertical axis. However, what if it wasn’t so straightforward? Such as..
With this enemy AI, the enemy does not know how the walls are laid out, it just knows it cannot bypass a wall and that it wants to move toward the player. As a player, we can see all the walls and can easily make that decision, but the computer sprite is blind to that, it just knows where an immediate wall is.
Another scenario that might just confuse the enemy.
Again, the player can see the pathway from the enemy to the player sprite. A native way would be to move the sprite toward the player in the vertical axis and then the horizontal axis, however that will get the enemy sprite stuck.
Without using a path-finding type routine, what we will have to do is make a random decision and then push the enemy sprite for the next 16 steps to continue in that direction. If it encounters a barrier, then we will have to make another decision at that point.
So the solution shown below is based on a random number.
Action: move in horizontal or vertical axis 16 pixel steps parallel to the obstacles and then make another decision. Decide between 2 random numbers.
Barriers on 2 sides. North and east, Case 5. South and east, case 6. North and west, Case 9. South and west, case 10.
Similar to the case above, we cannot simply move toward the player, as doing so can get the enemy sprite caught in a barrier. The enemy cannot look ahead, so in order to not get caught, we need to make a random decision on going to another position without getting caught. So, again our solution is based on a random number.
Only 1 case is illustrated.
Action: move in horizontal or vertical axis 16 pixel steps perpendicular to one of the 2 obstacles and then make another decision. Decide between 2 random numbers.
Barriers on 1 side. North, Case 1. South, case 2. East, Case 4. West, case 8.
Again, this will be randomly decided. But instead of doing a 50/50 decision, we will have to use a 33.3/33.3/33.3 based decision. We do this to try to eliminate the possibilities of getting stuck. So our decision is based on a random number from 1 to 3.
Only 1 case is illustrated.
Action: move in horizontal or vertical axis 16 pixel steps perpendicular or parallel to the obstacle and then make another decision. Decide between 3 random numbers.
So now, I’ll illustrate how this logic might work, using a random number and some possibilities of a number that sometimes takes us away from the player.
Our enemy in red is trying to make way to the player. The enemy has obstacles to the east and west. Case 12.
Random number decides to go south 16 pixels.
Case 14 is now in play (surrounded south, east, west) decision for case 14 is to move north 16 pixels.
Back to where we started.
We move north.
Now we are in the clear (Case 0)
We can then again move toward the player.
Whoops, we are blocked again. Now we have barriers to the east and south (case 6). Time for a 50/50 random number. Decide on north or west.
If we decide west, we encounter case 0 again and just end up back at the same place.
So, let’s show the north case.
We are again at case 0. There are no obstacles that the enemy can see, so it proceeds to move toward the player, however, there is a problem there is an obstacle to the southeast.
Remember earlier on when I said that moving toward the player in case 0, either move horizontally or vertically 16 pixels might be important. This is the case I was warning about. If we move diagonally southeast, we will run into an obstacle. So let’s not move our enemy southeast, we can choose either east or west, north or south. Since north would be out of bounds and away from the player, that direction is invalid. Since west is away from the player, that direction is also invalid. So we can choose east or south.
If we choose south, then we encounter case 6 again and would have to re-decide and repeat from earlier.
So, let’s then say our random number is then east.
Case 2 (barrier to south) is now in play. Choose from east or west. Let’s choose east.
Case 0, move toward the player, either horizontally or vertically.
We are now in Case 8, cannot move west.
Here is where the algorithm can fail, we have a 1 in 3 chance that the enemy will move toward the player. This is all decided randomly, as the enemy could go north or east. If we program a bias, we can give better odds that the enemy will go south. Even without the bias, if the enemy goes east, it will be a case 0 and move toward the player.
So, let’s show the 3 choices without a bias
In the first and second case, we are in case 0 whereas the enemy will move toward the player. In the third case, we move the enemy to just north of the player.
At this point, we have the same choice as last time, as we are in case 8, cannot move west.
Again, this is where we can program a bias to make it more possible to move toward the player.
This article has grown quite a bit from my original intention, so next time we will start to cover the code.
Until then, happy coding.