Jump to content


Photo

Algorithm confusion - for platform chasing A.I


  • This topic is locked This topic is locked
2 replies to this topic

#1 AndrewCay

AndrewCay

    Problem Solver

  • GMC Member
  • 520 posts
  • Version:GM:Studio

Posted 20 April 2012 - 05:41 AM

creation script
paths=ds_map_create();
section_ableto[0,0]=2;
section_ableto[0,1]=1;
section_ableto[0,2]=2;
ds_map_add(paths,"0,1 - 0",pth_test_0to1)
ds_map_add(paths,"0,2 - 0",pth_test_0to2)

section_ableto[1,0]=2;
section_ableto[1,1]=0;
section_ableto[1,2]=2;
ds_map_add(paths,"1,0 - 0",pth_test_1to0)
ds_map_add(paths,"1,2 - 0",pth_test_1to2)

section_ableto[2,0]=1;
section_ableto[2,1]=1;
ds_map_add(paths,"2,1 - 0",pth_test_2to1)

scr_zombie_find_section_ai

var  section_starter;
current_section=ds_grid_get(global.sections,x,y+bottom);
player_section=ds_grid_get(global.sections,obj_player.x,obj_player.y+obj_player.bottom);
//section_ableto

section_starter=current_section;

/*
This is how a zombie find's a section list leading too the player. It checks it's current section, then it checks the players.
If the player isn't within an easy grasp of the zombie (ie: out of the zombies section), then the zombie will want to find out how 
to get to him/her. 
    The algorithm uses the current_section, the player_section, and  previous_section variables.
*/


tree(5,current_section);// this is my methood called branching.

tree
var max_check, sec;
max_check=argument0;
sec=argument[1]// current_section;
fake_prio=ds_list_create();
tree_list_string=""
found=branch_start(max_check,sec);
if !(found==-1)
{
goto=found
}
ds_list_destroy(fake_prio);

branch_start
var v_left, v_c_section, v_last_amount, v_max_amount;
//v_left=argument0-1;
v_c_section=argument1;
v_max_amount=argument0;
v_last_amount=1000000;

//section_ableto
    for(i=0;i<=section_ableto[v_c_section,0];i+=1)// clears your lists,
        list[i]=-1;
    for(i=0;i<=section_ableto[v_c_section,0];i+=1)
    {
        list[i]=branches(v_c_section,i,v_max_amount) // goes through a loop finding all the routes   
    } 
    //for(i=0;i<=section_ableto[v_c_section,0];i+=1)
    //show_error(string(list[i]),false)
    for(i=0;i<=section_ableto[v_c_section,0];i+=1)
    {
        if list[i]>-1&&list[i]<v_last_amount
            v_last_amount=list[i]
    }
return v_last_amount;

Branches
//branches(v_c_section,i,v_max_amount)
/*
argument0 = previous section,
argument1 = current section,
argument2 = what to start subtracting from, if its smaller then 0 exit; 
*/
var v_previous_section, v_current_section, v_left, v_value;
v_previous_section=argument0;
v_current_section=argument1;
v_left=argument2;
v_value=-1;
if v_left>0
{
    v_left-=1;
    for(i=1;i<=section_ableto[v_current_section,0];i+=1)// sets the sections
    section[i]=-1;
    for(i=1;i<=section_ableto[v_current_section,0];i+=1)// starts looking through possible branches.
    {
        if (section_ableto[v_current_section,i]==player_section)// if the route leads to the player section.
            {
                v_value=section_ableto[v_current_section,i]// sets the returning value to this 
                break;
            }
        else
            section[i]=branches(v_current_section,i,v_left)
    }
    var v_most;
    v_most=10000;
    for(i=1;i<=section_ableto[v_current_section,0];i+=1)
    {
        if (section[i]<v_most&&section[i]>-1)
        {
            v_most=section[i];
            v_value=section[i]; 
        }
    }
    return v_value;
}
else
return v_value;

I'll make a drawing on what this is supposed to do, and how it works too clarify things up. Then i'll fully explain it with the picture, and the scripts functions.
Posted Image
Okay so you can see in the image a basic set up map. This is exactly how I set it up in my start event. I make a reasonable section in the room an assigned area. Each area is represented by its id, IE: 1, 2, 3 etc. Here is just a simple map, only three sections all of them except for one can access both the others.
Do you see the arrows? I have set these up as well in the create event using these "section_ableto[1,0]=2;". For ALL "section_ableto"'s I have them set up so that I can loop through them with ease. How I do this is by setting the y (section_ableto[x,"y"]) IF it is 0 too show how many different sections it can access. By this I can loop through each one like this
for(i=1;i<=section_ableto[v_current_section,0];i+=1)
When the y is greater then 0, the the values after it will be set with reachable sections.

So what i'm trying to achieve is this : If player is in section "0" and if it's not, then the algorithm I "tried" making will find a reasonable way to the desired section. My algorithm works like a branching system. It starts from the section it's in, from their it makes a loop going through every section it can reach - you can find this starting from the "branch_start" script. The main search is started in the branch_start script, for every reachable area it tries to check in a "branching" way (hard to explain really) until it hits the players section, OR if it has gone through at least 6 loops of branching.
My algorithm seems to work, at least when I test it, it says it found the players section using my system . . . but im sure there's probably a bug some where in the code. Now where my trouble really lies is making a list like this " 0 , 1 , 2 " < what that is supposed to be is a "section" list, basically giving the sections (in order from start too finish) needed to reach the player. So like the sections the "successful" branches made their way too.

If you can help me with my algorithm thank you so much! If you have something else that you think is better for platforming path finding please do I'm very grateful!
if this helps any - im doing this for a zombie game, it's like a zombie platform shooter based off of "Nazi zombies" from call of duty black ops. So the zombies need to be able to reach the player and find him/her. I'm also trying to do this in the most data saving way so not too take too much out of the max fps. When I normally do A.I it's for a top down game so I'm not familiar with platforming A.I .

P.S: Anything I need too add, or suggest adding?
  • 0

#2 connor4312

connor4312

    www.connorpeet.com

  • GMC Member
  • 896 posts
  • Version:None

Posted 20 April 2012 - 10:17 AM

So from what I can tell, you need a way to store the paths, and find the best one? What you would do is:

- Create two ds_grids, call them "success" and "fail", and create an array called "bestpoint"
- For each iteration of the branching algorithim:
---- Create a temporary array
---- Store each point of the branch in the arraybest
---- Increment a variable for each point in the path
---- If bestpoint[0] is greater than the distance from the current "pointer" to the player, write the current distance in bestpoint[0] and store the pointer x/y in bestpoint[1 and 2]
---- If the array successfully found the player, and if the value at (0,0) on success is greater than the current increment or it is null
------- Write the increment variable to (0,0) on success
------- Store the array in the grid
----If the array did NOT find the player, and if the value at (0,0) on failure is greater than the current increment or it is null, and is (0,0) on success is equal to null
------- Write bestpoint[0] to (0,0) on failure and write the values of the array up to that point
------- Store the array in the grid
---- Reset bestpoint
-If the grid failure is not empty, use that. Otherwise, use the grid success.

What this will do is store the most efficient path to the player, or find the path that will get nearest to the player.

Edited by connor4312, 20 April 2012 - 02:49 PM.

  • 0

#3 AndrewCay

AndrewCay

    Problem Solver

  • GMC Member
  • 520 posts
  • Version:GM:Studio

Posted 21 April 2012 - 02:51 AM

Hey man, I have no idea what you were doing, or if that was pseudo code or something. But I could not for the life of me "figure out" how to do that with what I am currently doing. But on the bright side, I perfected my scripts now fixing a lot of minor mistakes and added little touches so now it returns the route list. Thanks for your help any way connor4312. :)
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users