A Flash Developer Resource Site

Results 1 to 15 of 15

Thread: help on generating an area for path finding

  1. #1
    Senior Member
    Join Date
    Jun 2000
    Posts
    108

    help on generating an area for path finding

    Hi all,

    Does anybody still remember those good old tactic rpg games back to the Super Nintendo era? With user vs. computer in moving up army turn by turn and try to beat the heck of the opponent?

    I've been trying to create something like that but yet encounter much more problems then I expected~ I'm having trouble with path finding, but let's not get into that first... the major thing that I want to get it over with is 'generating an area for path finding', which means the boundary that my mc's are only allow to get to. I've tried searching but everyword that I put into the search here in flashkit doesn't seem to have any matches at all...

    The major problem is knowing rather there are walls in between the mcs' and areas that they can get to, I've tried a couple of tweak in my codes but that didn't work, and I thought of using path finding from node to node and make sure each node within the boundary can get to the MC (so sort of backward) But that seemed to be way too much work... So I'm wondering if anyone can give a few suggestion of what not or what I should do. Any suggestions are Good! Thank You
    BL

  2. #2
    -= phil =- d3s_inc's Avatar
    Join Date
    Oct 2002
    Posts
    610
    are you doing tilebased or artbased?

  3. #3
    Senior Member
    Join Date
    Jun 2000
    Posts
    108
    Hi d3s_inc,

    Thanks for replying!

    It's tile based, basically I've got a map worked out, clicking will suppose generate an area of available placements, but can't get what I want since right now the computer will generate placements even behind walls that there's no way that can get to... I took out my buggy path finding functions, 'cos I hope I can have this current problem solved first~ here are my codes:
    ____________________________________

    function build(){
    map = [[1,1,1,1,1,1,1,1,1,1,1,1,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,1,1,1,1,1,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,0,0,0,1],
    [1,0,0,0,1,1,1,1,1,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1,1,1,1]];

    var ox = 5;
    var oy = 10;

    tileH = 10;
    tileW = 10;
    mapH = map.length;
    mapW = map[0].length;

    attachMovie("empty","main",0);
    for (var i=0; i<mapH; i++){
    for (var j=0; j<mapW; j++){
    main.attachMovie("tile","t"+i+"_"+j, d++);
    var mt = main["t"+[i]+"_"+[j]];
    mt._x = j*tileW;
    mt._y = i*tileH;
    if (i == oy && j == ox){
    mt.gotoAndStop(5);
    } else {
    mt.gotoAndStop(map[i][j]+1);
    }
    }
    }
    }
    this.onMouseDown = function(){
    var ox = 5;
    var oy = 10;

    md++;
    if (md == 1){
    trace("generating Area");
    generateArea(oy,ox);
    } else if (md >= 2){
    dx = Math.floor(_xmouse/tileW);
    dy = Math.floor(_ymouse/tileH);
    if (main["t"+[dy]+"_"+[dx]]._currentframe == 4){
    trace ("dx = "+dx+" , dy = "+dy);
    md = 0;
    pathFind(oy,ox);
    }
    }
    }
    function generateArea(oy,ox){
    var maxY = 4;
    var maxX = 4;

    for (var i=oy; i<oy+maxY; i++){
    for (var j=ox; j<ox+maxX; j++){
    if (map[i][j] != 1){ //downRight
    main["t"+[i]+"_"+[j]].gotoAndStop(4);
    }
    if (map[i-maxY+1][j] != 1){ //upRight
    main["t"+[i-maxY+1]+"_"+[j]].gotoAndStop(4);
    }
    if (map[i][j-maxX+1] != 1){ //downLeft
    main["t"+[i]+"_"+[j-maxX+1]].gotoAndStop(4);
    }
    if (map[i-maxY+1][j-maxX+1] != 1){ //downLeft
    main["t"+[i-maxY+1]+"_"+[j-maxX+1]].gotoAndStop(4);
    }
    }
    }
    }
    __________

    If anyone have any suggestions of how about I should do this, please pitch in a few pointers? Thanks!
    BL

  4. #4
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    I have made something like this:
    http://www.tonypa.pri.ee/test/path.html

    It uses breadth-first pathfinding first to mark the tiles and then to make the actual path to the target tile.

  5. #5
    Senior Member
    Join Date
    Jun 2000
    Posts
    108
    thats exactly what I want to do Tonypa!

    did u try a more complex map and see if it worked smoothly? unfortunately i spent alooooong time on mine and I couldn't find a sucessful path... when I do my path search, it always get stuck in places like this... (w/ 'x's as walls and 'o' as the mc)

    xxx
    xox


    so i had functions that does reverse, but only works in a certain extend, can you tell me how do you do it?

    as for generating the area, can you teach me too?
    BL

  6. #6
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    Yes, my example work in any map. Just you cant let it go in big open space or it will take forever to go through every tile. Thats why you have to limit it by setting the umber of steps hero can walk.

    The breadth-first search always finds a path (if path exists) and it always returns the shortest path. But its very slow. It works well in Flash up to 5-6 steps, but after that gets slow.

    Im not generating any area specially for this, the code goes through tiles in a way, that it will generate the area itself AND returns the path, so it does 2 things in 1 code.

    Its pseudocode is explained here:
    http://www.cs.ncl.ac.uk/modules/2001...s/pathfinding/
    and
    http://roguelikedevelopment.org/~rog...t/&category=AI
    "Quick Pathfinding in a Dungeon" - Pieter Droogendijk
    also worth to read
    http://www.gamasutra.com/features/19...athfinding.htm

  7. #7
    Senior Member
    Join Date
    Jun 2000
    Posts
    108
    hi tonypa, those are pretty nice URLs you've got there! I think I sort of get the idea of Breadth-first-search now, but I'm not too sure how do you exactly put that to work, especially when u said:

    Im not generating any area specially for this, the code goes through tiles in a way, that it will generate the area itself AND returns the path, so it does 2 things in 1 code.
    so what did you do to create the area for your little path test in the first place ? can you explain a little more in depth? 'cos I think that is exactly what I've been looking for for my game Thanks!
    BL

  8. #8
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    Using this example:
    http://www.cs.ncl.ac.uk/modules/2001...s/pathfinding/

    When the breadth-first search code goes through tiles, I give each tile it adds to the Unchecked_Neighbours list, property steps, which is 1 more then its parents step. Note that tile is added to the list only if its walkable tile.

    Like this:

    | 9|10|11|14|15|
    |__|__|__|__|__|
    |12| 1| 2| 3|16|
    |__|__|__|__|__|
    |13| 4| 0| 5|17|
    |__|__|__|__|__|
    |18| 6| 7| 8|19|
    |__|__|__|__|__|
    |20|21|22|23|24|
    |__|__|__|__|__|

    starting tile 0 steps=0;
    its left, right, up and down neighbours steps=tile0.steps+1=1
    tile13 for example steps=tile4steps+1=2

    When tile is added to the list, its is on the area, so change its color.

    Now in each step you check if the current_tile.steps>hero_steps_allowed
    and if its bigger, stop the search.

    Lets say hero can make 2 steps, and search function reaches tile10, its steps property is 3, which is bigger then allowed steps and search ends.

    Now when user clicks on some tile, you check if it was marked by the serach to be on the allowed area. And since search has already found shortest path to it, you dont have to run it again.

  9. #9
    Senior Member
    Join Date
    Jun 2000
    Posts
    108
    Hi Tonypa,

    When the breadth-first search code goes through tiles, I give each tile it adds to the Unchecked_Neighbours list, property steps, which is 1 more then its parents step....
    starting tile 0 steps=0;
    its left, right, up and down neighbours steps=tile0.steps+1=1
    tile13 for example steps=tile4steps+1=2
    so does this mean within each tile there are a given property in 'steps' when you set up the map? I'm kinda confused , can you please clarify how the map is organized? And does that mean when I create my map I'd need to insert the tile numbers (9,10,11,14,15) within my map array?

    Thanks for your help, I'm almost getting it, please help me through this
    BL

  10. #10
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    I am using the system from my tutorials. It creates object for each tile which are placed in the "game" object:
    http://www.tonypa.pri.ee/tbw/index.html

    The pathfinding function also creates object for each tile, but it calls tiles "nodes" and they are all placed in the "path" object. The "steps" property is assigned to the nodes in the path object.

    Check the attached fla.

  11. #11
    Senior Member
    Join Date
    Jun 2000
    Posts
    108
    Wow Tonypa, thanks, that makes ALOT more sense now! Sorry for this late reply, I wanted to make sure I understand your codes first incase if there are any questions

    Just a minor thing though, you know when you used the if statement to check whether the character (ob) is at the center of any tile? I didn't quite understand the '%' within the statement, even after I read the actionscript dictionary

    Either way, Thank You SO much, I'll show a demo whenever I can, Thank You!
    BL

  12. #12
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    Originally posted by 4eyes
    Just a minor thing though, you know when you used the if statement to check whether the character (ob) is at the center of any tile? I didn't quite understand the '%' within the statement, even after I read the actionscript dictionary
    % is modulo. It returns remainder of division. The way I used it, was to make sure position x can be divided by size of tile tileW precisely.

    Better use example:
    lets say x is 34 and tileW is 10.
    x%tileW would return 4
    (34/10=3,4 now it uses integer from division 3 to multiply by 10, which is 30. Then 30 is reduced from 34 and the answer is 4)

    I was checking x%tileW to be equal with 0. That can happen only if x is 10, 20, 30, 40 etc, tileW multiplied by any integer.

  13. #13
    curiouser and curiouser LittleRed's Avatar
    Join Date
    Mar 2004
    Location
    Nottingham
    Posts
    335
    Originally posted by tonypa

    When the breadth-first search code goes through tiles, I give each tile it adds to the Unchecked_Neighbours list, property steps, which is 1 more then its parents step. Note that tile is added to the list only if its walkable tile.

    Like this:

    | 9|10|11|14|15|
    |__|__|__|__|__|
    |12| 1| 2| 3|16|
    |__|__|__|__|__|
    |13| 4| 0| 5|17|
    |__|__|__|__|__|
    |18| 6| 7| 8|19|
    |__|__|__|__|__|
    |20|21|22|23|24|
    |__|__|__|__|__|

    just so that I completely understand this (and thanks Tonypa - as ever you've made difficult concepts very easy to understand),
    if my breadth-first pathfinder doesn't examine diagonals, and is only looking at up to three steps away, then the search pattern would be:
    Code:
    ** ** ** 13 ** ** **
    ** ** 15 05 14 ** **
    ** 17 07 01 06 16 **
    24 12 04 00 02 08 18
    ** 23 11 03 09 19 **
    ** ** 22 10 20 ** **
    ** ** ** 21 ** ** **

  14. #14
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    That looks like correct pattern, LittleRed

  15. #15
    curiouser and curiouser LittleRed's Avatar
    Join Date
    Mar 2004
    Location
    Nottingham
    Posts
    335
    thanks - I just wanted to make sure that I understood the theory!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center