Spastic fantastic, Enemy movement problems part 1

So there is a bit of a problem with the enemy movements, it’s been an ongoing problem, but so far I have ignored it, the enemy movement is spastic, almost like a drunk.

It’s hard to describe it verbally and impossible with a photo, but here a video showing the effect.

https://youtu.be/qoDyVk5zeUA

It’s actually pretty funny.

The answer to why the enemy is doing this motion is pretty simple to explain. When the enemy sprite touches an obstacle, we are using a random number to decide on our next move. However, the random number could have the enemy run parallel to the obstacle where it makes the random decision again which could place it parallel again or back to the original position. All of this in rapid motion makes you enemy appear to spaz out.

We need to somehow calm down your enemy, yet we still want to use randomization so your enemy can’t be predictable and yet can still move toward you.

A number of fixes come to mind. The first type is based on a path-finding method. There are a number of different types of path-finding, but the most popular is called A Star. It’s the most used and the most quoted when programmers are trying to find a way for an enemy sprite to find it’s way toward a player.

However, there is a problem with using what is considered the gold standard to path-finding. It’s time-consuming. Perhaps not as time-consuming as other path-finding techniques, but still too time-consuming for this game.

Here’s the problem with path-finding, in order for an enemy to plot a position from itself to you, we have to scan the array where all the obstacles are, we then assigning a number to each tile where there is a valid move in incrementing order from your player to the enemy moving outbound. So, in the final square, you would place a 1, the next ring outwards, you will place a 2 (on all valid moves). The next ring after that (on all valid moves), you place a 3 and continue on until the start position of the enemy. You then find which path is the shortest by adding up the numbers on a valid path. Seems simple enough, however, you will have to scan the array each time there is a movement and scan the array for each enemy.

The size of the array is 15 character blocks wide and 10 character blocks high for a total of 150 objects.

So the number of times we have to scan the array is once per enemy, per movement.

150 tiles, times 4 enemies is 600 times each time you move to a different position. Furthermore, you have to convert pixel-based sprite positions to character-based positions each time. It’s far too much to do for a real-time game not turn based.

If someone comes up with a fast assembly based on that will work in real-time for FASE, I’d be happy in incorporate it….Hint. Hint.

But alas, we’re cooking this thing up in pure C, so we’ll have to deal with the constraints my brain can handle. So instead of using a path-finding technique that will bog down the game, let’s see how clever we can get with our method and keep our enemy sprites from being spastic.

Two fixes come to mind, using our constraints.

1) Place some bias to the decision of where the enemy moves.
Right now, if an enemy touches a barrier and there is a clear pathway to the player, we must wait until the random number decides to choose a number to move to your direction. If we could make a bias to move in your direction and not wait until a randomization to point in your direction, this could solve the issue.

2) Move the enemy away from the obstacle more and then make a random decision as 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 back 16 tiles back and then make a random decision.

3) Remove the randomization.
The jerky movement is due to making a random decision once it hits an obstacle. Why not remove the randomization and just set the enemy to chase the player, just not cross a barrier when doing so.

Let’s start with the first improvement, placing some bias to the decision.

Now, we could call the random number for each of the 16 scenarios and adjust the range in each if statement, but calling the number once saves on memory. This would limit or expand the randomization. Expanding the randomization would allow you to bias by adding additional scenarios that could steer the enemy

Example code

if (barrierPosition == 1)//cannot move north
{	
    decision = (SHR3 % 4);//our random number from the macro , range is 1 to 4
    if (decision == 1)
    {
        enemyY++;//go south
    }
    if (decision == 2)
    {
        enemyX++;//go east
    }
    if (decision == 3)
    {
        enemyX--;//go west
    }
    if (decision == 4)
    {
        enemyX--;//go west
    }
}

Now, here we are using an example scenario. A random number between 1 and 4 are generated. We have a bias to go west as it is called if the random number is either 3 or 4. This means that it is twice as likely to go west.

Rather than writing out a number of if conditions, we can also use the logical OR operand.

That would take on the form of:

if (barrierPosition == 1)//cannot move north
{		
    //move south, east, west		
    if (decision == 1 || decision == 4)
    {
        enemyY++;//go south
    }
    if (decision == 2)
    {
        enemyX++;//go east
    }
    if (decision == 3)
    {
        enemyX--;//go west
    }
}

So, we are twice as likely to go south than in any other direction. As it would be more desirable to perpendicular to the obstacle rather than travel alongside it. Why, when you go perpendicular, the next time the function is called, it will most likely fall under the very first if statement

if (barrierPosition == 0)

Which simply moves the enemy toward the player.

The entire logic looks like:

    if (barrierPosition == 0) 
	{
        //move toward player
        //move toward player x and y        
        if (enemyX > playerX) {
            enemyX--;//go west
        }
        if (enemyX  playerY {
            enemyY--;//go north
        }
        if (enemyY < playerY) {
            enemyY++;//go south
        }
    }
    
    if (barrierPosition == 1)//cannot move north
    {        
        //move south, east, west        
        if (decision == 1 || decision == 4) {
            enemyY++;//go south
        }
        if (decision == 2) {
            enemyX++;//go east
        }
        if (decision == 3) {
            enemyX--;//go west
        }
    }

    if (barrierPosition == 2)//cannot move south
    {        
        //move north, east, west        
        if (decision == 1 || decision == 4) {
            enemyY--;//go north
        }
        if (decision == 2) {
            enemyX++;//go east
        }
        if (decision == 3) {
            enemyX--;//go west
        }
    }
    
    if (barrierPosition == 3)//cannot move north or south
    {        
        //move east, west
        if (decision == 1 || decision == 4) {
            enemyX++;//go east
        }
        if (decision == 2 || decision == 3) {
            enemyX--;//go west
        }
    }
    
    if (barrierPosition == 4)//cannot move east
    {        
        //move north, south, west
        if (decision == 1) {
            enemyY--;//go north
        }
        if (decision == 2) {
            enemyY++;//go south
        }
        if (decision == 3 || decision == 4) {
            enemyX--;//go west
        }
    }
    
    if (barrierPosition == 5)//cannot move north or east
    {
        //move south, west
        if (decision == 1 || decision == 4) {
            enemyY++;//go south
        }
        if (decision == 2 || decision == 3) {
            enemyX--;//go west
        }
    }
    
    if (barrierPosition == 6)//cannot move south or east
    {        
        //move north, west
        if (decision == 1 || decision == 4) {            
            enemyY--;//go north
        }
        if (decision == 2 || decision == 3) {
            enemyX--;//go west
        }
    }
    
    if (barrierPosition == 7)//cannot move north, south, east
    {
        //move west
        enemyX--;//go west
    }
    
    if (barrierPosition == 8)//cannot move west
    {        
        //move north, south, east
        if (decision == 1 || decision == 4) {
            enemyX++;//go east
        }
        if (decision == 2) {            
            enemyY--;//go north
        }
        if (decision == 3) {
            enemyY++;//go south
        }
    }

    if (barrierPosition == 9)//cannot move north, west
    {        
        //move south, east
        if (decision == 1 || decision == 4) {
            enemyY++;//go south
        }
        if (decision == 2 || decision == 3) {
            enemyX ++;//go east
        }
    }
    
    if (barrierPosition == 10)//cannot move south, west
    {        
        //move north, east
        if (decision == 1 || decision == 4) {            
            enemyY--;//go north
        }
        if (decision == 2 || decision == 3) {
            enemyX++;//go east
        }
    }
    
    if (barrierPosition == 11)//cannot move north, south, west
    {        
        //move east
        enemyX++;//go east
    }
    
    if (barrierPosition == 12)//cannot move east, west
    {        
        //move north, south
        if (decision == 1 || decision == 4) {            
            enemyY--;//go north
        }
        if (decision == 2 || decision == 3) {
            enemyY++;//go south
        }
    }
    
    if (barrierPosition == 13)//cannot move north, east, west
    {        
        //move south
        enemyY++;//go south
    }
    
    if (barrierPosition == 14)//cannot south, east, west
    {
        //move north
        enemyY--;//go north
    }
    
    if (barrierPosition == 15)//cannot move any direction
    {
        //do nothing
    }

Of course, there are many opportunities the enemy will get stuck.

What’s the memory cost of the additional OR statements? 192 additional bytes.

Is it worth it? That’s an iffy question, the enemy sprites are still spastic when they touch an obstacle.

We could continue to try to stack the odds in favor. Let’s give that a try.

Let’s adjust our random number.

decision = (SHR3 % 10);//our random number from the macro, range is 1 to 10

Then let’s adjust our conditional statements to something like

if (barrierPosition == 1)//cannot move north
{		
    //move south, east, west		
    if (decision == 1)
    {
        enemyX++;//go east
    }
    if (decision == 2)
    {
        enemyX--;//go west
    }
    if (decision > 2)//biased
    {
        enemyY++;//go south
    }
}

So any random number from 2 to 10 will choose going south which increases our threshold.

Using this method only cost 16 additional bytes of memory, so this would be the better way to go.

Here’s our code dump for this method

decision = (SHR3 % 10);//our random number from the macro , range is 1 to 10
//let's make a decision based on a random direction
    
if (barrierPosition == 0)
{
    //move toward player
    //move toward player x and y        
    if (enemyX > playerX)
    {
        enemyX--;//go west
    }
    if (enemyX  playerY)
    {
        enemyY--;//go north
    }
    if (enemyY  2)//biased
    {
        enemyY++;//go south
    }
}
    
if (barrierPosition == 2)//cannot move south
{        
    //move north, east, west        
    if (decision == 1)
    {
        enemyX++;//go east
    }
    if (decision == 2)
    {
        enemyX--;//go west
    }
    if (decision > 2)//biased
    {
        enemyY--;//go north
    }
}
    
if (barrierPosition == 3)//cannot move north or south
{        
    //move east, west
    if (decision > 4)
    {
        enemyX++;//go east
    }
    if (decision  2)//biased
    {
        enemyX--;//go west
    }
}
    
if (barrierPosition == 5)//cannot move north or east
{
    //move south, west
    if (decision > 4)
    {
        enemyY++;//go south
    }
    if (decision  4)
    {            
        enemyY--;//go north
    }
    if (decision  2)
    {
        enemyX++;//go east
    }
}

if (barrierPosition == 9)//cannot move north, west
{        
    //move south, east
    if (decision > 4)
    {
        enemyY++;//go south
    }
    if (decision  4)
    {            
        enemyY--;//go north
    }
    if (decision  4)
    {            
        enemyY--;//go north
    }
    if (decision < 6)
    {
        enemyY++;//go south
    }
}
    
if (barrierPosition == 13)//cannot move north, east, west
{        
    //move south
    enemyY++;//go south
}

if (barrierPosition == 14)//cannot south, east, west
{
    //move north
    enemyY--;//go north
    }

if (barrierPosition == 15)//cannot move any direction
{
    //do nothing
}

Another way we can place additional bias is by using the && operator. We can also have the enemy move toward the player if while in the bias statement, we add an additional draw toward the player.

An example of this would be.

if (barrierPosition == 1)//cannot move north
{		
    //move south, east, west		
    if (decision == 1)
    {
        enemyX++;//go east
    }
    if (decision == 2)
    {
        enemyX--;//go west
    }
    if (decision > 2 && enemyY < playerY)//biased
    {
        enemyY++;//go south
    }
}

However, be cautious as this starts to become a memory hog. In fact, so much, I’m not going to do a code dump, however, if you want to pursue this method, you should be able to extrapolate from the code sample above.

We can also get rid of any jittery motion altogether by removing the randomization altogether. This is a very popular method with many games. The enemy will make a beeline for the player unless blocked by an obstacle.

It’s pretty straightforward and predictable, but the movement is smooth.

https://youtu.be/V3S2LSaFdIc

It’s exactly the same as we had enemies in artificial stupidity except they now respect obstacles.

Here’s our code dump

    if (barrierPosition == 0)    {
        //move toward player
        //move toward player x and y        
        if (enemyX > playerX)        {
            enemyX--;//go west
        }
        if (enemyX  playerY)        {
            enemyY--;//go north
        }
        if (enemyY < playerY)        {
            enemyY++;//go south
        }
    }
    
    if (barrierPosition == 1)//cannot move north
    {        
        //move south, east, west        
        if (enemyX  playerX)        {
            enemyX--;//go west
        }
        if (enemyY  playerY)        {
            enemyY--;//go north
        }
    }
    
    if (barrierPosition == 3)//cannot move north or south
    {        
        //move east, west
        if (enemyX > playerX)        {
            enemyX--;//go west
        }
        if (enemyX  playerX)        {
            enemyX--;//go west
        }
        if (enemyY > playerY)        {
            enemyY--;//go north
        }
        if (enemyY  playerX)        {
            enemyX--;//go west
        }
        if (enemyY  playerX)        {
            enemyX--;//go west
        }

        if (enemyY > playerY)        {
            enemyY--;//go north
        }
    }
    
    if (barrierPosition == 7)//cannot move north, south, east
    {
        //move west
        enemyX--;//go west
    }
    
    if (barrierPosition == 8)//cannot move west
    {        
        //move north, south, east
        if (enemyX  playerY)        {
            enemyY--;//go north
        }
        if (enemyY < playerY)        {
            enemyY++;//go south
        }
    }

    if (barrierPosition == 9)//cannot move north, west
    {        
        //move south, east
        if (enemyX < playerX)        {
            enemyX++;//go east
        }
        if (enemyY  playerY)        {
            enemyY--;//go north
        }
        if (enemyY < playerY)        {
            enemyY++;//go south
        }
    }
    
    if (barrierPosition == 13)//cannot move north, east, west
    {        
        //move south
        enemyY++;//go south
    }
    
    if (barrierPosition == 14)//cannot south, east, west
    {
        //move north
        enemyY--;//go north
    }
    
    if (barrierPosition == 15)//cannot move any direction
    {
        //do nothing
    }

That’s all that’s popping in my head, for now, hopefully, the code dumps will keep you busy for a little while, the next time I approach this subject, we will cover the movement of the enemy away from the obstacle before making another decision.

Advertisements

Author: andydansby

I'm a hobbyist coder working with the ZX Spectrum. Living in New York state near the Syracuse area. I grew up in Virgina. The first computer my parents bought for me was a Timex Sinclair 2068.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s