Alvarian Tales Project - March 2013

[rdc]

Now a problem I'm having is this. Since objects move pixel-by-pixel, bounding blocks can sometimes fill an extra cell row and/or column of cells, depending on how they land on the grid...

I am not sure what you describing here. If I am reading this right, an object may not exactly align on the grid. This would be natural since they move by pixel rather than by grid cells. I actually thought about that when I was thinking about this. I would just pick the cell that contains the majority of the object, or simply a cell that the object occupies, and use that as the path starting point. It wouldn't make that big of difference since the object moves by pixel anyway.

If this isn't the problem, maybe you could elaborate a bit.

[mrToad]

Yea that's pretty much what I mean. The base of a tree, for instance, is sometimes 4 squares by 4 squares blocked off, and sometimes it goes 5 squares by 4 squares, switching back and forth as the object that is path-finding moves on its way. I'll ignore it for now and see if it even matters.

Just extra info:
The grid that the objects use to pathfind is quickly set up uniquely for each object, and follows the object. This is because the maps are not just 1 screen size, they can be four or five screens wide, and are panned. So that I don't have a really huge grid for path finding, each object has about a 1-screen size grid relative to its location. The grid is always centered over the object as the object moves, and other objects around it are blocked off on the grid as they enter the grid space.

Phew, that's a mouth full.

[rdc]

So, the grid is centered on the actor pathfinding? That should make the process much more simple. You should always have a good starting point for the pathfinding process.

You can run a cull before you do the pathfinding and eliminate any fully or partially covered cells, since an actor wouldn't be able to fit in the cell anyway. This would include static objects and other actors.

Even though this may take a small bit of time, you'll end up saving some time in the pathfinding process, since you don't have to look at those at all and can concentrate on cells you know the actor can enter. That is the reason I think using a grid the size of the actor will help. It gives a scale you can use to test cells and should eliminate the peep-hole problem you mentioned.

[mrToad]

Yup, it's centered over the actor pathfinding.

By removing the cells he cannot enter, isn't that the same as just blocking them off, or closing them? I do that before the algorithm is run. Or do you mean actually removing them from the cell array before running the algorithm?

The peep-hole problem only disappears when you search the entire space of each cell, for any portion of a bounding box inside. But before I was just checking the center pixel of the cell. It's a better idea to check all of it. So that problem is gone now, thankyou. :)

[rdc]

By removing the cells he cannot enter, isn't that the same as just blocking them off, or closing them? But I think you mean actually removing them from the cell array before running the algorithm. Interesting... Maybe that would save time. If that's what you mean, I will give that a try

Yeah, I was just thinking of adding them to the closed list so that aren't checked during pathfinding. Removing them from the array may not be worth the trouble if they are already on the closed list, but you could try it both ways and see if there is any noticeable speed difference.

As far as culling, any cell that is even partially occupied could be discarded since the actor wouldn't be able to get into that cell. As I said, determining the intersection may take a bit of time, but it may pay off in the pathfinding process. Trail and error here will tell the story.

Just some ideas to explore.

[mrToad]

Code: Select all

Function obj_go_path(o As Integer) As Integer
   
    If AStarObj <> o Then AStar__Setup(o)
   
    With obj(o)
   
    Dim As Integer csx = (CELL_W\2-1)
    Dim As Integer csy = (CELL_H\2-1)
    Dim As Single acx = ((.pa.x-(.x+.b.x)) / .pa.sw)
    Dim As Single acy = ((.pa.y-(.y+.b.y)) / .pa.sh)
    Dim As Integer cex = csx + acx
    Dim As Integer cey = csy + acy
   
    if cex < 0 then cex = 0
    if cey < 0 then cey = 0
    If cex > CELL_W-1 Then cex = CELL_W-1
    If cey > CELL_H-1 Then cey = CELL_H-1

    ASTAR_CellClearAll()
    ASTAR_CellSetStart(csx,csy)
    ASTAR_CellSetEnd(cex,cey)
   
    For x as integer = 0 to CELL_W -1
        For y as integer = 0 to CELL_H -1
            Dim As Integer x1a,y1a,x2a,y2a,x1b,y1b,x2b,y2b
            x1a = (-320+.x+.b.x+.pa.sw\2)+x*.pa.sw
            y1a = (-240+.y+.b.y+.pa.sh\2)+y*.pa.sh
            x2a = (-320+.x+.b.x+.pa.sw\2)+x*.pa.sw+.pa.sw-1
            y2a = (-240+.y+.b.y+.pa.sh\2)+y*.pa.sh+.pa.sh-1

            For n As Integer = 1 To n_o
                If obj(n).ng.en Then
                    x1b = obj(n).x+obj(n).ng.x1
                    y1b = obj(n).y+obj(n).ng.y1
                    x2b = obj(n).x+obj(n).ng.x2
                    y2b = obj(n).y+obj(n).ng.y2
                    If inRange2(x1a,y1a,x2a,y2a,x1b,y1b,x2b,y2b) Then
                        ASTAR_CellSetSolid(x,y,TRUE)
                    EndIf
                EndIf
            Next
        Next
    Next
   
    ASTAR_Compute()
    AStar__GivePathTo(o)



Here's what I'm doing for the pathfinder.
.pa.sw and .pa.sh stand for path stepwidth and path stepheight, in other words grid cell dimensions.
.x+.b.x and .y+.b.y is just finding the base point of the object (its feet.)
.ng = nogo or bounding box.

inRange2 checks that no point of either box is within the four points of the other box. So each cell cannot have a point within a bounding box, and no bounding box point can be within a cell. Not sure how this will run with a couple dozen pathfinders... but I don't know of any more efficient way.

[rdc]

It looks pretty good to me. I suspect the most time is spent in the actual pathfinding, so I bet this will run just fine.

[mrToad]

The bounding boxes aligning irregularly with the pathfinder's grid is an issue. It changes the path constantly, and sometimes catches the pathfinder under an unexpected closed cell. See this YouTube video

So I'm trying to figure out how to get the closed cells to stay consistent and never change unless the bounding box dimensions change.

[rdc]

Yeah, I see what you mean. Since they are fixed objects, they should remain stationary. Just a guess here: It looks like it might be a precision error creeping in when you calculate the boxes as the screen moves. This is going to be the case if the sprite is an odd size like 17. Are you using integer or floats? You might need to use float calculations for better precision and then convert to integer for the screen.

[mrToad]

I think it's the way the dimensions of the bounding box are divided among the cells.

A bounding box of 32 pixels in width can be divided as 16 in the first cell, and 16 in the next, two cells. OR... if the pathfinder moves over 8 pixels, the same box will be 8,16,8, using three cells. Half cell, full cell, half cell. That's because any portion of the bounding box in the cell marks it closed.

If the pathfinder only moved his cell width each step, it would never be a problem. But he must move pixel by pixel.

[rdc]

OK, I am wondering if it is a problem between two different coordinate systems? Sort of like world coordinates vs. display coordinates. You have the pathfinder coordinate system and object coordinate system. Maybe this is the problem. You may just have to go with your original idea of a fixed system for all objects on the map. Either that or work out some transformation system if in fact this is the problem. You original approach may be easier and work just as well in the end.

[mrToad]

Appreciate all your help man! I'll see what I can do, and maybe try the original idea. Just don't want a huge grid. But if only moving a short distance, might not matter how big the grid is.

[rdc]

I wish I could be more help. It is a puzzling problem. The main thing is get something that works. :) You can always tweak it if need be.

[mrToad]

I believe I have solved the problem, lol. Although the pathfinding actor moves pixel by pixel, his grid doesn't need to. It can move by the grid dimensions. It will wait until the actor has moved at least the width/height of a cell before moving over. Kind of like waiting for the actor to walk into the next cell, and then bumping over to keep him in the center.

This actually came to me while taking a nap lol.

So the stationary objects, at least, will always block the same amount of cells. (Because the bounding boxes always land/align with the actor's grid the same way.) Moving objects still vary the cells blocked, but that would be the case even if the grid was one big shared one... rather than relative to the actor.

By the way, you helped a lot. Just bouncing things back and forth really progresses the ideas.

[rdc]

Good to hear. I also get solutions to problems while napping. :) Glad you got it worked out.