## Alvarian Tales Project - March 2013

User projects written in or related to FreeBASIC.
Galeon
Posts: 563
Joined: Apr 08, 2009 5:30
Location: Philippines
Contact:
E.K.Virtanen
Posts: 785
Joined: May 28, 2005 9:19
Location: Finland
Yep, by looking the graphics this can definately be game i like to play. Now keep on coding and give something to download :)
Posts: 353
Joined: Jun 07, 2005 23:03
Location: USA
Contact:
July, 2010 Update. See original post.
agamemnus
Posts: 1842
Joined: Jun 02, 2005 4:48
- NPCs can path-find using the A* algorithm. Since this is not a tile-based engine, the general area around them is overlain with a mesh of 8x8 squares, instead of per-pixel pathfinding. If 8x8 turns out too slow with more NPCs, might step up to 16.

Interesting solution.

Instead of 8x8 squares, you can also try recursively a smaller grid... find the path in the big grid, then use that path to refine your smaller grid and so on.. it'd be a lot of work, though...
Dr_D
Posts: 2388
Joined: May 27, 2005 4:59
Contact:
Hey guys... I've been a fan of this for a while, so I just wanted to throw in my two cents.

Here's the jist of it...

Obviously, since you're already using A*, you know that tiles aren't the key in any way. But... pixels aren't either and I think that's a bad way to go.

Strategically placed way-points, and sub-way-points, and maybe even ((sub)-sub) way-points unlock the magic, in my opinion. I guess the whole thing comes down to writing an algo to "break your level down" intro a grid, be it 2d, 3d, or whatever it may be, and then "wrapping" the A* algorithm around it.
rdc
Posts: 1713
Joined: May 27, 2005 17:22
Location: Texas, USA
Contact:
Since you are using sprites the size of the grid cells can the size of the sprites. If the sprites are 32x32 than you can create a grid at this size. This will reduce the number of calculations needed. It isn't really necessary to add multiple points within the sprite size radius. To move from one cell to another all you need is a simple line of sight movement. To make the movement a bit more realistic, you can add some noise to the line of sight movement.
relsoft
Posts: 1767
Joined: May 27, 2005 10:34
Location: Philippines
Contact:
Looks great dude!!!
Posts: 353
Joined: Jun 07, 2005 23:03
Location: USA
Contact:
This engine uses images that are all different sizes, aligned to an 8x8 pixel grid. The houses, for instance, are one solid image. But the windows, doors, and other details are overlain as separate objects. They layer correctly because everything has a z coordinate, so they can be lifted off the ground.

The pathfinding is a another 8x8 pixel grid lain over the general area of an NPC. It fills in squares on that grid if it detects any no-go-zones from objects:

< image removed, see later post. >

Pathfind grid:
< image removed, see later post. >

This last image is actually not drawn correctly, because the path is off by one square, lol. But you get the idea.

Last edited by mrToad on Jul 11, 2010 20:19, edited 1 time in total.
agamemnus
Posts: 1842
Joined: Jun 02, 2005 4:48
So in fact it IS just a grid-based pathfinding algorithm. ;) Nevertheless, good work!
rdc
Posts: 1713
Joined: May 27, 2005 17:22
Location: Texas, USA
Contact:
mrToad wrote:This engine uses images that are all different sizes, aligned to an 8x8 pixel grid. The houses, for instance, are one solid image. But the windows, doors, and other details are overlain as separate objects. They layer correctly because everything has a z coordinate, so they can be lifted off the ground.

That was what I was trying to get to. From looking at your pictures you are calculating 3-4 points inside the size of the sprite. All you need is one point per size of sprite. If you create a grid with a cell size equal to the size of the sprite (whatever it is), you can then plot a single point per cell and just move from one cell to the next using line of sight movement. The sprite movement granularity is going to be the sprite bounding box (you can't move closer to the building than the bounding box) so there is no reason to plot multiple points inside the sprite. This will reduce the number of calculations needed for your path finding.

In fact you don't even need one point per cell. All you really need is a set of points that are in line-of-sight of each other, so you can trim the number of points needed to describe a path. A fence for example would block line of sight so that the path would go around it. This is what Dr. D was speaking to when he was talking about way points.

Pathfinding is computationally expensive, since you need to revisit a cell many times, and by reducing the number of cells visited, you can make the algo more efficient.

Of course I may be missing the point of what you are doing here too.
Posts: 353
Joined: Jun 07, 2005 23:03
Location: USA
Contact:
Hmm, yea I'm a bit confused. If you're referring to the 1 or 2 big circles on the screenshots, those have nothing to do with pathfinding. That's just a sensing area to engage combat. I replaced the pictures in the previous post with slightly better ones:

I'll try to explain what's going on. A map is drawn simply by objects drawing themselves at their own coordinates. (There's no Map array.) Each map object can be placed at any x/y location, but most often are snapped-to-8x8 pixel grid. The map objects are all different sizes. They have bounding boxes (I call 'em no-go zones) which are a set of coords like: x1,y1,x2,y2 relative to the object position. (See the red boxes around the rocks.) This is so other moving objects (which move pixel by pixel) cannot move over this part of the object.

The pathfinding checks a large grid area around a moving object, and closes grid boxes where the nogo zones overlay.

@rdc, I'm not sure what you mean by calculating 3-4 points inside the sprites? And what about waypoints? Not sure how that would be done. I don't mean to make you work, lol. But any tips for less calculations are definitely useful.

One issue I'm going to have is grid boxes are not filled in because the pixel checked happens to not be covered by any object's no-go zone, but just above and below, it is covered. So it leaves a hairline space between two objects, and the moving object thinks it can pass through. To resolve, I either have to leave no such spaces anywhere, or check more than one point for a no-go zone.
agamemnus
Posts: 1842
Joined: Jun 02, 2005 4:48
So buildings themselves are positioned per pixel, not in groups of 8?
rdc
Posts: 1713
Joined: May 27, 2005 17:22
Location: Texas, USA
Contact:
mrToad wrote:@rdc, I'm not sure what you mean by calculating 3-4 points inside the sprites? And what about waypoints? Not sure how that would be done. I don't mean to make you work, lol. But any tips for less calculations are definitely useful.

It is kind of hard to describe. Here is some code from my RLEngine which dynamically creates a grid for generating a dungeon. Even though this is dungeon code, the idea is applicable for building a grid for pathfinding.

Code: Select all

`#Define mapw 100 'map width#Define maph 100 'map height'Grid cell size (width and height)Const csize = 10'Grid dimensions.Const gw = mapw \ csizeConst gh = maph \ csize'Grid cell structure.Type celltype   cellcoord As mcoord 'The cell position.   room As Integer     'Room id. This is an index into the room array.End TypeDim Shared grid(1 To gw, 1 To gh) As celltype'Creates the grid.   For i = 1 To gw       For j = 1 To gh          grid(i, j).cellcoord.x = gx          grid(i, j).cellcoord.y = gy           grid(i, j).Room = emptycell           gy += csize      Next      gy = 1      gx += csize   Next`

What this does is define a grid that covers the level map. The grid is a two-dimensional array defined by gw and gh. These are calculated values shown in the Const definitions. The two For Next loops just iterate through the grid array, defining the x,y coordinates of the grid cells. When the loops are finished, you have a two dimensional array where each cell has an x, y coordinate that corresponds to an x, y coordinate on the level map.

Now, you can use this same idea to generate your paths. Where I have mapw, maph you would use the current screen resolution or whatever area you are using for your map. Where I have csize, you would would need two entries, one for the sprite width and one for the sprite height (or width and height of the sprite bounding box). You could then calculate the gw and gh values.

In the For-Next loops you would use the sprite width and height where I use the csize values. This will give you a two dimensional grid that matches the screen size, with cells the same size as your sprite. You then go through your pathfinding algorithm using this grid as your base grid. Since each cell is the same size as the sprite, there is less to calculate.

You can also close off cells that the sprite won't fit into. For example, if a cell is half filled with fence, then the sprite can't enter that cell, so you add it to the closed list and don't have to worry about it. You could iterate through the array ahead of time and cull any cells that the sprite can't enter, leaving you with a smaller set of cells that you have to worry about.

I hope this explains a bit what I was talking about. This is just an idea for you; it certainly doesn't represent the only way to do it.
Posts: 353
Joined: Jun 07, 2005 23:03
Location: USA
Contact:
Yes that's much clearer this time. Thank you! Now I see I would simply set the grid cell dimensions of an object to the same object's bounding box dimensions, as it's a logical setup. And if any portion of any bounding box lands within a cell, it's blocked off.

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. Like, as an object path-finds, the objects around him land differently on his grid as he moves pixel by pixel. So that a bounding box can layer over 3 cells at one moment, and then just 2 the next. This is because the grid follows the object each pixel, and is always calculating a new path. Even if the grid were to jump x/y the amount of each cell's width/height, other object's bounding boxes are different sizes, and I think the problem would be the same. It's not a terrible problem, but it's not the way it should be.

I really can't think of any solution right now. Can you imagine what I'm saying?