Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[EnigmaticHat]

So my grid-based A* pathfinding function I had that didn't quite work?  I tried and I tried to make it work and I finally found the problem.  At the start of the function I created a list of 8 adjacencies, as in, literally just a list of moves that count as valid.  As it turns out, one of the entries in this list was a duplicate.  So the function only believed that monsters could move in 7 directions instead of 8.  As a result, whenever they had to move diagonally NW, the monsters would take a zigzaging pattern because they couldn't move diagonally.  Hindsight is 20/20, I assumed the problem would be more complicated than it actually was.

BTW, there's only one guide that has ever made A* make enough sense to me so that I could actually implement it, and that's this one.  If you ever want to make a roguelike or something it could help you out.

[MagmaMcFry]

<regex>

I'm not sure what you're trying to do here, but it seems you are trying to capture a BIND statement with all its SYM and KEY attributes at once.

What I would suggest you do is use

Code: [Select]

/\[[^\[\]]*\]/gto capture all tags, split for tokens by ":", and then work with the list of lists you generated instead of the raw text. There's no use going that overboard with regular expressions.

[Bumber]

<regex>

I'm not sure what you're trying to do here, but it seems you are trying to capture a BIND statement with all its SYM and KEY attributes at once.

What I would suggest you do is use

Code: [Select]

/\[[^\[\]]*\]/gto capture all tags, split for tokens by ":", and then work with the list of lists you generated instead of the raw text. There's no use going that overboard with regular expressions.

Each BIND should be grouped with its following keybind tags. I seem to have pulled it off like this:

Code: (Regex) [Select]

/(\s*\[BIND:.+\n+(?:\s*\[(?!BIND).+\n+)*)/g

Code: (Explanation) [Select]

(\s*            = Begin the group and accept any whitespace.
\[BIND:.+\n+    = Match the string "[BIND:" and continue to take the rest of the line. Accept extra newlines.
(?:\s*          = Begin the subgroup (non-capturing) that will accept non-BIND lines, allowing whitespace at the beginning of each.
\[(?!BIND).+\n+ = Accept "[" but not followed by "BIND". Continue to take the rest of the line and accept extra newlines.
)*)             = End the subgroup, allowing any number of non-Bind lines. End the group.Now, in theory this is supposed to break the segments down further:

Code: (Regex) [Select]

/\s*\[BIND:([\w]+):([\w]+)\](.*)\n+(?:(\s*\[[^\]]*\])(.*)\n+)*/

Code: (Explanation) [Select]

\s*\[BIND:         = Skip whitespace and "[BIND:".
([\w]+)            = Select the Command, which is alphanumeric and _.
:([\w]+)\]         = Skip over the ":", select the Repeat setting, skip over "]"
(.*)\n+            = Select the rest of the line as Comments, allow extra newlines.
(?:(\s*\[[^\]]*\]) = Begin a subgroup for the other lines. Select whitespace, "[", any number of non-"]" characters, and then "]". Stop selecting.
(.*)\n+            = Select the rest of the line as Comments, allow extra newlines.
)*                 = End the subgroup, allow any number of these lines.The combined result is the same as this:

Code: (Regex) [Select]

/\s*\[BIND:([\w]+):([\w]+)\](.*)\n+(?:(\s*\[(?!BIND:)[^\]+]+\])(.*)\n+)*/gBoth methods have the issue that it only takes the last non-BIND line.

[breadman]

Basically, what happens is that each () capturing group captures at most one expression.  When you have such a group inside a repeating expression, each match for that group overwrites the previous match.  So yes, you're matching each [SYM] expression in turn, but only the last one is retained.  (That's what that note means in the Explanation box on your linked site.)

In essence, you want a single regular expression to return an array of results, with the second match of each result being an array.  Unfortunately, the regular expression engines available don't support that, so you'll have to loop over your regular expression results to process them into what you need.

As MagmaMcFry suggests, it's convenient here to use a simple regular expression that collects all tags, allowing you to use a simpler split function to process them.  Loop over the list of tags, creating a new array for each BIND tag, and appending to that array for each SYM or KEY tag.

Alternatively, you can use one more complex regular expression to collect the BIND tag parameters in a pair of matches, and the whole set of SYM/KEY tags in another match.  (/\[BIND:(\w+)\w+)\](.*)\n+((?:\[(?!BIND:)[^]]*\](?:[^[]|\n)*)*)/gm)  Then you'll need to loop over the results of that expression, and use a second regular expression to parse the individual SYM/KEY tags out of the string containing them.  Unfortunately, this system is both harder to implement correctly and more likely to break if anything changes.

By the way, [\w] is equivalent to [w] in some engines and \w in others, so it's probably best to avoid it.

[Shadowlord]

By the way, [\w] is equivalent to [w] in some engines and \w in others, so it's probably best to avoid it.

What, really?

[Bumber]

Basically, what happens is that each () capturing group captures at most one expression.  When you have such a group inside a repeating expression, each match for that group overwrites the previous match.

Good to know, thanks. The new and improved version is this:

Code: (Regex) [Select]

/\s*\[BIND:(\w+):(\w+)\](.*)\n+((?:\s*\[(?!BIND:).*\n+)*)/gI can then iterate through the non-BIND lines with a simple:

Code: (Regex) [Select]

/(.*\n+)/g

[Antsan]

BTW, there's only one guide that has ever made A* make enough sense to me so that I could actually implement it, and that's this one.  If you ever want to make a roguelike or something it could help you out.

That's a nice article. About this, though:

8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.

So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest.

I think this might be optimized by using H=min(H1,H2,…,Hn) as the heuristic when H1,H2,…,Hn are the heuristics for the targets. Should save a lot of exploration when there's two targets in opposite directions, for instance, by not exploring sidewards.
If you have different kinds of targets with weights (between 0 and 1) you can take these into account, too:
H=min(w1*H1,…,wn*Hn)

[itisnotlogical]

Couldn't you just use the regular distance formula to find the distance to each resource? The worst I can imagine happening is some sort of discrepancy where it checks the top-left corner of the tile as opposed to the center of the tile, but that's down to individual implementation of the tile map and A*/Dijkstra.

If you're checking per-tile then that many square-root operations might be a performance hit, but I'd have maybe pre-defined "regions" of resources, which might be hundreds of tiles but considered as a single coordinate for a resource gatherer looking for the nearest tile.

[Shadowlord]

The whole point of a pathfinding function is lost if you simply distance formula into Mordor!

[Putnam]

Couldn't you just use the regular distance formula to find the distance to each resource?

Distance through unpathable tiles isn't real distance. Dijkstra's algorithm is the regular distance formula anywhere that involves unpathable tiles or terrain.

[i2amroy]

I think this might be optimized by using H=min(H1,H2,…,Hn) as the heuristic when H1,H2,…,Hn are the heuristics for the targets. Should save a lot of exploration when there's two targets in opposite directions, for instance, by not exploring sidewards.
If you have different kinds of targets with weights (between 0 and 1) you can take these into account, too:
H=min(w1*H1,…,wn*Hn)

I'd like to re-emphasize heuristic use. There are very, very few cases in the world of games (or the real world, for that matter), where you actually need "the shortest" path as opposed to just a "short" path, and there are worlds of efficiency differences between the two (seeing factors of 10x or greater in the amount of checks that you need to do to find "the shortest" path as opposed to just a "short" one is not exactly uncommon). And to emphasize the matter, if you ever notice the actual way that you travel around you'll probably find that the vast majority of the time you don't actually take the "shortest" path. Ever walked down the columns and then up the row in a parking lot rather than cutting between the cars? How about walking on the sidewalk around a field rather than straight through the middle? Humans are actually pretty bad about finding the true "shortest path" in complex environments, and we are much more predisposed to paths that we know or that are already outlined (cached) than those that are truly optimized for distance. (As such not only can you get huge speed increases, but you can get a realism bonus too ).

Unless you are working in something that actually requires the shortest path instead of just doing pathfinding your first thought shouldn't be "how can I implement pathfinding here?" but should rather be "what heuristic can I use to make my results 'good enough'?".

(I found a great article about this once, but sadly I can't find it again right now. )

[Shadowlord]

To be fair, there are reasons not to take the "shortest path" in those situations. Spending as little time as possible in the middle of the road, and ticks, for example.

[Reelya]

In those cases the field and middle of the road can be given a higher move cost. With maybe a lower weight to road crossing at junctions. A* isn't about the literal shortest path, only the lowest weight path.

Also for the field, it would be nice if people cut the corners now and then, and some people trekked through the literal middle of the field to save time. Make some people prone to ignoring the terrain costs for the field, and for others, have a cumulative cost based on how many field tiles you've crossed. So for some people cutting the corner of a field is preferable to walking right to the corner.

I also like the idea that terrain gets degraded into a dirt path after a lot of walkers have been over it. So eventually the few trailblazers form a visible path right through the middle of the field corner to corner and then regular people decide to use that.

[i2amroy]

To be fair, there are reasons not to take the "shortest path" in those situations. Spending as little time as possible in the middle of the road, and ticks, for example.

There's other, similar, cases where taking the "almost shortest" path even on similarly weighted terrain is more common for humans. An example is that many times humans prioritize the shortest immediate path over the shortest overall path; i.e. they enjoy a sense of progress. For example (black is start point, red is goal point):

Spoiler (click to show/hide)

Path 2 is actually the shorter path here by a little bit. However if exposed to this scenario a large number of people, even those more familiar with the area, are more likely to take path 1 instead of path 2. This is because the start of path 1 provides a fairly large amount of immediate progress towards your goal, while on the other hand taking path two actually requires you to move farther away from your goal in the short term in order to be able to perform better over the longer path. There's a reason why the marshmallow test (you can have this marshmallow now, or if you wait 10 minutes I'll give you another marshmallow and you can have two) is hard; humans tend to prioritize immediate progress towards a goal over a setback now for overall improved gains later. And when combined with the fact that once a person has traveled a (potentially not shortest) path once (caching) they are more likely to take that route again even if a slightly faster route still exists, it can result in even those people who regularly travel the area taking suboptimal paths.

Of course, it doesn't really matter which path is the real shortest for most intents and purposes, because both paths are within ~5% of the same length and both would easily suffice for most pathfinding purposes. So if we already know that being "almost good enough" will work, we can get some massive reductions in the amount of space we need to check. Here's two examples from the A* wikipedia page that let you visually see the difference in the cells checked (and thus time taken) between searching for the "shortest" path vs. searching for a "short" path.

Spoiler (click to show/hide)

"Shortest"

"Short"

[Antsan]

That difference is really damn impressive.

Here's an article that displays well why using Lisp as a functional language or to learn functional programming is not that good:
http://web.archive.org/web/20140711171812/http://symbo1ics.com/blog/?p=1495
Specifically take a look at this snippet:

But even so, using CLOS to emulate algebraic data types is like stapling a few pages together with 10 inch galvanized nails with a sledgehammer. And what benefit do we get? We’d need to do some wizardry to get pattern matching and other benefits. (CL-MONAD is a library which takes this approach, and also defines pattern matching macros, and monads. (Though, monads are really only useful when you have tail recursion, compile-time types, etc., but that’s a story for another post.))

Emphasis by me. A lot of the theory behind functional programming seems completely useless in Lisp.