121
Programming / Re: Pathfinding implementation not working the way I want it to.
« on: March 25, 2010, 06:35:41 AM »
So then why would my program be giving such a weird result?
Show Posts
This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
122
Programming / Pathfinding implementation not working the way I want it to.
« on: March 25, 2010, 05:24:55 AM »
Hi.
I just wrote up some code to do the A* pathfinding algorithm for digging tunnels in a dungeon generator for a Roguelike game, and I'm getting some odd results. When I use it to dig a tunnel through free space between two points, I got this:
But that doesn't look good. I'd like to have it look like a straightish diagonal line between the two points, something sort of like what would come out of Bresenham's algorithm. Why is it goofy like that? I use a rounded-down Euclidean H-function (with sqrt), a same-cost G-function (i.e. move to any neighbor including diagonals is the same cost), and the open list priority queue is implemented via binary heap with supplementary tiebreaking key to enforce LIFO tie behavior (so it's more of a "stack" than a "queue" when it comes to ties) among nodes/tiles with equal F-cost. Neighbors are checked in a clockwise pattern starting at the upper-left.
If I switch the heap over to FIFO behavior (like a proper "queue"), I get this:
which looks a bit better, but the algorithm also seems to explore many more squares. And it's still got that "curve" which doesn't look too good. (Strange; it reminds me of the graph of the square root function. Is there something significant about that?) Both tunnels seem to have the same length (32 squares). I presume it has something to do with how it handles the multiple existent shortest paths between the points, but how do I get it to give me "nice" ones?
The code (C++) for the G, H functions is this:
And yes, I've tested the heap code to make sure it didn't have any bugs in it. I've tried various descriptions of the A* algorithm and have redone this like 4 or 5 times with the same results... which suggests I'm missing something, but I can't figure out what it is. What is going on here? Using alternative heuristics like, e.g. diagonal (max of x/y distances) doesn't help it, though it's not curved anymore, it has either a long straight segment before diagonaling down (FIFO) or it diagonals down, then goes straight for a while, before a short diagonal up to the destination point (LIFO).
I just wrote up some code to do the A* pathfinding algorithm for digging tunnels in a dungeon generator for a Roguelike game, and I'm getting some odd results. When I use it to dig a tunnel through free space between two points, I got this:
Code: [Select]
################################################################################
################################################################################
################################################################################
################################################################################
####.###########################################################################
#####.##########################################################################
######.#########################################################################
#######.########################################################################
########.#######################################################################
#########.######################################################################
##########.########################.############################################
###########.######################.#############################################
############.##################...##############################################
#############.##############...#################################################
##############.########.....####################################################
###############.##.....#########################################################
################..##############################################################
But that doesn't look good. I'd like to have it look like a straightish diagonal line between the two points, something sort of like what would come out of Bresenham's algorithm. Why is it goofy like that? I use a rounded-down Euclidean H-function (with sqrt), a same-cost G-function (i.e. move to any neighbor including diagonals is the same cost), and the open list priority queue is implemented via binary heap with supplementary tiebreaking key to enforce LIFO tie behavior (so it's more of a "stack" than a "queue" when it comes to ties) among nodes/tiles with equal F-cost. Neighbors are checked in a clockwise pattern starting at the upper-left.
If I switch the heap over to FIFO behavior (like a proper "queue"), I get this:
Code: [Select]
################################################################################
################################################################################
################################################################################
####.......#####################################################################
###########.......##############################################################
##################.....#########################################################
#######################.....####################################################
############################...#################################################
###############################...##############################################
##################################.#############################################
###################################.############################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
which looks a bit better, but the algorithm also seems to explore many more squares. And it's still got that "curve" which doesn't look too good. (Strange; it reminds me of the graph of the square root function. Is there something significant about that?) Both tunnels seem to have the same length (32 squares). I presume it has something to do with how it handles the multiple existent shortest paths between the points, but how do I get it to give me "nice" ones?
The code (C++) for the G, H functions is this:
Code: [Select]
float GCostFuncs_Flat(u16 y1, u16 x1, u16 y2, u16 x2)
{
return(BASE_COST);
}
float HCostFuncs_Euclidean(u16 y1, u16 x1, u16 y2, u16 x2)
{
double ydist(y2), xdist(x2);
ydist -= y1;
xdist -= x1;
return(floor(sqrt(ydist*ydist + xdist*xdist))*BASE_COST);
}
And yes, I've tested the heap code to make sure it didn't have any bugs in it. I've tried various descriptions of the A* algorithm and have redone this like 4 or 5 times with the same results... which suggests I'm missing something, but I can't figure out what it is. What is going on here? Using alternative heuristics like, e.g. diagonal (max of x/y distances) doesn't help it, though it's not curved anymore, it has either a long straight segment before diagonaling down (FIFO) or it diagonals down, then goes straight for a while, before a short diagonal up to the destination point (LIFO).
123
Programming / Re: Questions about programming a Roguelike game
« on: January 30, 2010, 09:26:38 PM »First up, choose a language you are comfortable with and familiar with using it. If you plan on learning a language by coding a roguelike, I would suggest starting on a small roguelike attempt first. Trying to achieve a large goal in a new language is difficult at best. As for which is more popular... download a few roguelikes and see...
On map/level generation... there are plenty of articles about this, the pitfalls and solutions. Path finding can be as simple or as complex as you choose to make it. And lets define slow... You are typically working with a small map (lets say 80x20), which even if you have to visit EVERY location four times you are only looking at 6400 visits to each location. Now this may have been a problem pre-1995, but I am fairly sure a dual-quad-core running the latest Radeon ANSI-8192 GPU will have no problems performing this task before you can blink.
My suggestion - go write some simple tests... see how the code works... this will help understand what makes things slow or fast.
Hmm. It seems like C++ is used more often, at least for newer roguelikes.
As for the map generator, I suppose then one doesn't need a really complicated pathfinding method? And I was thinking bigger levels than that, like 80x80 at least.
124
Programming / Re: Questions about programming a Roguelike game
« on: January 29, 2010, 10:42:58 PM »How can one make a good level generator that generates levels without having tunnels remove the walls from rooms
There are many ways to prevent that. Start from placing rooms so that they don't have walls next to each other, or if they have the walls are removed or a special corridor is made between them to connect them.
When you make corridors it's good not to make them travel over another rooms (this may be prevented with pathfinding or connecting rooms that are close).
Pathfinding is probably the tool you need to solve problem situations.
I thought about the use of a pathfinding algorithm, but I've heard stuff about it being really slow. Or would one only use the pathfinding algorithm some times (i.e. if we can't create a viable corridor between two points directly, switch to the pathfinding method?)? Also, what's so bad about crossing through a room, as opposed to bulldozing its walls? All it'd do is make more doorways.
125
Programming / Questions about programming a Roguelike game
« on: January 29, 2010, 06:54:14 PM »
Hi.
I have a couple questions:
1. Which one of C or C++ is more often used for making Roguelike games? I've heard of other languages being used as well, but for games written with one of these two, which is the more often used one, and why?
2. How can one make a good level generator that generates levels without having tunnels remove the walls from rooms (piercing a room is fine, so long as it doesn't take off stretches of wall, or knock off a corner), or "double up" (i.e. parallel each other so close no wall is in between them)?
I have a couple questions:
1. Which one of C or C++ is more often used for making Roguelike games? I've heard of other languages being used as well, but for games written with one of these two, which is the more often used one, and why?
2. How can one make a good level generator that generates levels without having tunnels remove the walls from rooms (piercing a room is fine, so long as it doesn't take off stretches of wall, or knock off a corner), or "double up" (i.e. parallel each other so close no wall is in between them)?