What's the best method to send multiple pathfinding directions?

[Khranos]

Hi everybody!

I'm currently working on an 2.5D isometric game which will have dynamic pathfinding and terrain creation (the user manually creates the terrain, the coordinates are logged, and the pathfinding adapts to the changes). The pathfinding will give directions to little people-like entities when they want to reach a specific tile.

(example of potential terrain)

My current grid system works by using this code to create a coordinate grid within a table in the format "grid[xTile][yTile]": (also contains additional info to get the actual coordinates for x and y in the world).

Code: Select all

local function gridLoad()
  if preload then
    for x=1, gridSizeX do
      grid[x] = {}
      for y=1, gridSizeY do
        grid[x][y] = { x = 0, y = 0}
        if x == gridSizeX and y == gridSizeY then
          preload = false
        end
      end
    end
  end
end

A visual example after drawing everything is as follows:


After this table is created, a new table (terrain) is created which logs the x and y grid position (plus a few things like image name) of any tiles that have been placed into the world. This allows me to iterate through that table and find any matching grid coordinates when selecting a location for my pathfinding.

Currently, I'm subtracting the desired finish point from the starting point, check if the number is negative or positive, then iterate up or down through the table terrain (based upon if the number was positive/negative) looking for potential tiles available leading toward the desired point.

However, the roadblock I'm currently at is that I have no idea how I should give the info to the people-like entities mentioned earlier. A table seems like the best way to store the info, but if I'm giving directions to multiple entities at once it'll likely overwrite the directions for the first.

So, to summarize the question -- what would be the best way to save and send multiple lists of directions to each entity?

Thank you to anybody who attempts to help by giving advice or steering me in the right direction.

http://pastebin.com/R0873aQv (pastebin to the current main.lua)
(Attached will also be the .love file)

[mr_happy]

At the outset I'll say that I don't know Lua very well.

If I understand correctly and you want to avoid recomputing, why not just give each entity a single list of co-ordinates with a marker (pair) between each path: {100, 100}... {145, 97}, {-1, -1}, {100, 100}...{152, 99} or whatever with {-1, -1} denoting the end of a list.

My guess is that this would perform badly if the list grew to any size. Depending upon the complexity of the terrain and whether or not you're checking other entities etc for collisions it might be cheaper to re-compute at each step using a simple algorithm eg breadth-first search.

In another (OO) language I'd use a list of lists, an array of lists or a linked list (I have one of these in my current fledgling 'project' https://vimeo.com/170473669).

Might I ask why you're storing multiple routes per entity when they can only use one at a time anyway? If those routes are unchanging it might be better to have a 'communal' network (set of nodes) that any entity can latch on to to get to a particular place. So much depends upon your exact requirements.

[Khranos]

Even if that's the case, I do greatly appreciate the reply -- many people don't take the time.

The method you're mentioning is actually similar to what I was initially attempting, but I was having issues with tables being rewritten (if I were to keep directions in only one) and also as I think you mentioned, it'd be very impractical to create a new table specifically catered to each entity (even if temporarily) each time new directions are needed.

The problem persists in the fact that these routes are in fact subject to changing, which is why I'll need a way to ensure correct directions are being both updated and given to each entity (of which hundreds could be present at once). I feel I should probably rephrase my question just a bit to eliminate some confusion -- what would be the best method from a technical standpoint to save and send a list of coordinate directions in association with my method of generating coordinates without creating a large amount of stress on the engine?

Also, if I'm understanding your last paragraph properly, the second screenshot I have in the main post shows a type of node-like system that anything could latch onto if it so pleased (every node can give its coordinate among other things when referenced).

[mr_happy]

I don't see any alternative to using a table as it's the only container available (well other than files or writing to bitmaps!)

Why are the routes changing - is the destination/target moving, are there moving obstacles or does the terrain/map change?

You might be able to optimise your lists in some way depending upon which applies. I guess you've already thought of this but if there are oodles of entities you'd probably want the path updates throttled to avoid massive spikes when things change.

Just to possibly help with your over-writing problem, my storage is like this example:

Code: Select all

parts[i].coords = track.urquad

So any number of 'parts' can have the 'track.urquad' list, where:

Code: Select all

 
track.urquad = {
{128, 64},
...

and my entity (axle in this case) accesses the x, y co-ordinates like this:

Code: Select all

parts[axle[i].node].coords[axle[i].index][1]
parts[axle[i].node].coords[axle[i].index][2]

But of course, my paths are mostly unchanging (apart from switchable junctions). The method could work in your case by assigning new lists to the 'track' table but performance would probably be poor.