This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Path finding

Path finding
by on (#44650)
So I've been working on a strategy/tactical rpg game of sorts. It's sort of a cross of Fire Emblem and Romance of the Three Kingdoms.

Code:
http://never-obsolete.110mb.com/nesdev/img/Dom_00.JPG


Right now I'm trying to come up with a way to generate movement grids. What complicates the issue is that each terrain type has it's own movement speed associated with it. You end up with situations where you could move farther by going around terrain then through it.

I was wondering if anyone here has experience with path finding algorithms, I seem to be at a loss on how to go about it. All my ideas have too much hardcoded or require too much ram/time (that's if they even work :)).

edit: I can only get the image to show by pasting into url bar, otherwise it says something about a missing index.htm. Strange since I know there is one.

by on (#44652)
Sounds like a fun project!

Well, I had to do a bit of 'path finding' on my latest project, but it's not as involved as yours is, from how it sounds. But, I would probably do something like:

For each direction that you can travel, get an index from a map in RAM, which you probably already have. Take the maximum distance that the object can move, and when you check the first space, subtract that metatiles' "speed slow down" from the allowed movement of the object. If the objects max movement space is not yet zero, somehow save the current variable that is being used (maybe via stack), and check the square to the left of that. You would probably have to push this one on the stack, too, if it's not yet zero, so you could check other tiles around the current one you are on. It's hard to explain what I mean :'(

Basically I'm thinking you could have a max movement for each one of the objects on the screen, and you check the movement declination (?) of each successive tile. I'm guessing you will end up having to take a bit of time, but it probably won't be too noticeable.

This does sound a bit complicated haha Good luck!

by on (#44653)
Are you trying to explain the A* algorithm?

EDIT: blast you phpBB 2

by on (#44654)
mmm... Yeah, kinda looks like the idea I was trying to explain, although I'm not sure if there'd be an 'end goal,' as much as there is an 'as far as you can go' factor to it. Looks about right though!

by on (#44692)
Thanks for the info. After reading the link, this is what I came up with:

I have an array sized for the largest possible movement grid (1byte =1square). In my example I used 9x9 grid, 4 squares per direction.

so each square has the following data fields
-moveAvailable = move points left from square
-queued = if square has been queued already
-reachable = if square is reachable from starting square
-checked = if sqaure has already been processed
-movePenalty = cost of moving over square, this is tied to metatile data

some abreviations:
-x = starting square (only used at the begining)
-p = parent square
-c = child square

Code:
   1. set each square to NULL ($00)
   2. set x.moveAvailable = MAX movement
   3. push x coordinates onto queue
   
-->4. pull next coordinate from queue (set -> p)
   5. if (p.moveAvailable > 0)
      {
        for each adjacent square to p:
        {
          if ((c.checked = 0) && (c.queued = 0))
          {
            set c.moveAvailable = (p.moveAvailable - c.movePenalty)
            set c.queued = 1
            push coordinates onto queue
          }
          else
          {
            if ( (p.moveAvailable - c.movePenalty) > c.moveAvailable) )
            {
              set c.moveAvailable = (p.moveAvailable - c.movePenalty)
              if (c.queued = 0)
              {
                set c.queued = 1
                push coordinates onto queue
              }
          }
        }
      }
      if (p.moveAvailable >= 0)
        p.reachable = 1
      else
        p.reachable = 0
      p.checked = 1

   6. if (queue not empty), goto step #4


I prototyped it in vb6 and it seemed to work. Let see how porting it goes.