Top Down Cover Finding( warning computationally expensive)

S

spoonsinbunnies

Guest
GM Version:1.4.1763
Target Platform: Any
Download: <N/A>
Links: https://spoonsinbunnies.itch.io/topdowncoverexample a quick example(mouse to add delete a to toggle extra draw)

Summary:
Lets be fair top down shooters don't get a lot of love, so if you've ever wanted your enemies to find cover without nodes, well I had to make a solution so I figured I would share my results.

Tutorial:
Okay firsts things first, this solution is very, very computationally expensive, also pronounced lag inducing nightmare if ran every frame. Use will require careful consideration to be useful, and there is probably better solutions where the user wont charge the object its avoiding before diving around a corner(aka didn't feel writing weighted A* based on how many enemies could see each cell to avoid crossing open areas for cover, it simply finds the closest cover not checking its path).

Okay still with me? Lets set the scene, its 2009 and you want to make a top down shooter, because it hasn't been played out before, and you notice most top down shooters have the same enemies over and over, charge until in range and if your in range stop and shoot, rarely do enemies find cover, and if they do its special cover that only works in two directions, i.e. a thin barrier. What happens if you want a box and your enemies to dance around it avoiding line of sight before popping out and shooting? Well I sort of figured out how to do that, so I figured worst case I share and it helps no one.

Anyway this works by combining two very simple concepts that I opted to keep as two scripts with one referencing the other. I'll explain as best I can as we go and hopefully even if you just copy paste, you can understand what the scripts doing at least a little. The first script is so simple I don't know if I can put more than a few sentences to describe it and it is as follow. I called this script covered_check

Code:
covered=true;  //bot assumes its in cover
for(i=-1; i<ds_list_size(avoid); i++)//loops through bots who have shot it recently
{
    shooter=ds_list_find_value(avoid,i);
    if shooter>0
    if !collision_line(argument0,argument1,shooter.x,shooter.y,wall,false,false)//if there is not a wall between them
    covered=false;//bot is out in the open
}
if collision_point(argument0,argument1,wall,true,false)//set walls to not in cover
covered=false;
if argument0<16 or argument1<16 or argument0>room_width-16 or argument1>room_width-16
covered=false
if covered=true//if bot is in cover, goal is set to current position
{
    coverx=argument0;
    covery=argument1;
}
Pretty easy to follow, or it is to me, put simply it goes through a list and using and x and y arguments looks for a wall between it and the object in the list. If there's not a wall your not covered. there's also some preventative lines near the end so when you check where a wall is or outside the room you get told that is not a viable spot for cover. And finally if that spot is viable for cover we save the variables to use the mpgrid system to find our way there.

Now the second code is a little harder to follow and Ill show it in chunks so you can see what we are doing, if you just want the goods scroll down to the last example the first and bottom is all you need, the rest is for you to use and see to understand the system. So we have a code that can check a area and tell us if anything from a list has a line of sight. How should we pick where to check? Ideally we should pick as close to the player as we can.

So for this I decided to make a square grid spiral, we start one square grid above and two to the right, we move left then down right then up, and if we hit the starting corner we simply move out again and repeat, so here's an early code that does that, I feel like this bit of code is fun to not run in a loop and have reset and could be a cool thing to implement as something else as well, a square spiral is kind of cool to watch in my opinion. variables

Code:
    layer=1;//this sets how wide of grid squares you are searching
    xst=(round(x/32)*32;//align the check to a argument0xargument0 grid move to top right + 1 space
    xc=xst+64
    yst=(round(y/32)*32;
    yc=yst-32
    checkd=1//this is the direction on the square you are searching
and the loop, note everything is written in reverse, this stops more than one thing from happening with only one run through
Code:
        if checkd=4//if moving up the right side
        yc-=32;
        if checkd=3//if moving right along the bottom
        xc+=32;
        if checkd=2//if moving down the left side
        yc+=32;
        if checkd=1//if moving left across the top
        xc-=32;
        if yc=(yst-32*layer && checkd=4//if at the top left corner moving up
        {
            layer+=1;//move up one and right two to start the next rectangle
            xc+=64;
            yc-=32;
            checkd=1;//start moveing left
        }
        if xc=xst+32*layer && checkd=3//if at the bottom right corner start moving up
        checkd=4;
        if yc=yst+32*layer && checkd=2//if at the bottom left side start moving right
        checkd=3;
        if xc=xst+32*layer && checkd=1//if at the top left corner start moving left
        checkd=2;
if you add this code to an object and draw something using xc and yc you will see something that spirals out and away from our character and on a grid. so now all that's left is to optimize our code a bit and combine our two functions to make a something that spirals away from the player and then checks until it finds a place no one on the list has line of sight to, that's the closest place in cover.

First optimization I did was a simple replacement of all the 32s with argument 0 and 64 with argument0 + argument0, that makes the grid size easy to change. as we just plug it in when we reference our script the second change, was more personal taste, Im a little ocd, and my screen fits 42 lines of code, my final code was 44 so I decided to not have an xst and a yst in the loop, I could replace those with round(x or y/argument0)*argument0 anyway, and while its a little less readable I felt it was worth it for me to not have to scroll to see the whole script while tweaking it.

Lastly before the loop I added a check where you were to stop your player from running for cover if no one could see him anyway, and added a stopping point so if there is no possible cover the do until loop doesn't crash our game out. For this I decided to use either the room height or width whichever was bigger/the grid size.

Finally after a day of work we ended up with this.
Code:
covered_check(x,y);//checks if everyone who has shot the bot is blocked by a wa
if covered=false//if the bot is out of cover
{
  if room_width>room_height
   quit=room_width/32;
   else
    quit=room_height/32;
    layer=1;//this sets how wide of grid squares you are searching
    xc=(round(x/argument0)*argument0)+argument0+argument0;//align the check to a grid move up 1 right 2 spaces
    yc=(round(y/argument0)*argument0)-argument0;
    checkd=1//this is the direction on the square you are searching
    do
    {
        if checkd=4//if moving up the right side
        yc-=argument0;
        if checkd=3//if moving right along the bottom
        xc+=argument0;
        if checkd=2//if moving down the left side
        yc+=argument0;
        if checkd=1//if moving left across the top
        xc-=argument0;
        covered_check(xc,yc);//check this spot
        if yc=(round(y/argument0)*argument0)-argument0*layer && checkd=4//if at the top left corner moving up
        {
            layer+=1;//move up one and right two to start the next rectangle
            xc+=argument0+argument0;
            yc-=argument0;
            checkd=1;//start moveing left
        }
        if xc=(round(x/argument0)*argument0)+argument0*layer && checkd=3//if at the bottom right corner start moving up
        checkd=4;
        if yc=(round(y/argument0)*argument0)+argument0*layer && checkd=2//if at the bottom left side start moving right
        checkd=3;
        if xc=(round(x/argument0)*argument0)-argument0*layer && checkd=1//if at the top left corner start moving left
        checkd=2;
    }
    until covered=true or layer>quit
    if covered=false
    {
        coverx=x
       covery=y
    }
}
So that's it two scripts (and you only call one the second uses the first) that find you the closest x and y with a wall between them and every object on a list. Like I said earlier this is a heavy script, you don't want to call it every frame. It works well if every time an enemy is shot it adds the shooter to the list and runs this once after for framerate reasons.

I made a small example with visuals that runs from the mouse and clicks I may dump on itch.io after uploading this, If you have ideas on how to improve this (and I kinda do, mainly only doing half a square by finding the lists average direction. but testing is needed) feel free to comment.

Happy coding. Ive been up two days straight gonna take a nap.
 
Last edited by a moderator:
I

Inconmon

Guest
I thought about it for a moment, and I would run a script across each obj_cover. The script finds the directions towards player objects and stores locations (potentially predefined and stored in the cover object, or just opposite) into a list. If cover is one directional it would filter out cover that isn't matching.
Then the script finds the closest spot to the ai and sets it as pathing target.

Thoughts?
 
S

spoonsinbunnies

Guest
I thought about it for a moment, and I would run a script across each obj_cover. The script finds the directions towards player objects and stores locations (potentially predefined and stored in the cover object, or just opposite) into a list. If cover is one directional it would filter out cover that isn't matching.
Then the script finds the closest spot to the ai and sets it as pathing target.

Thoughts?
that was originally a process I used tbh, and it worked quite fine for a quicker version, I just wasn't happy that the ai would cling to walls when it wasn't nessecary, by using a whole grid of an area one can find cover that's far from the wall but is still blocked by the walls view instead of running up to the wall, this also made the separate steering behavior not force ai trying to perch at a full corner from completely pushing each other out into the field by giving more potentially covered areas.
 
Code:
for(i=-1; i<ds_list_size(avoid); i++)//loops through bots who have shot it recently
{
    shooter=ds_list_find_value(avoid,i);
    if shooter>0
    if !collision_line(argument0,argument1,shooter.x,shooter.y,wall,false,false)//if there is not a wall between them
    covered=false;//bot is out in the open
}
This bit here is a for loop accessing a ds list, which presumably has the id's of objects that can fire?

The user FrosyCat can explain this better than me, but I think I'm right in saying this: a "with" loop directly accessing those objects (sharing a parent) would be better.

Something about how "with" works is better computationally, and essentially would be doing the same as looping through the list. It just removes the need for storing the list, accessing it, and getting the list size. Plus some other aspects that are to do with the engine, or whatnot, that are beyond me explaining.

This is something I've seen for myself, so will 100% say it's worth seeing how much difference it makes.
 
Top