[Reaper_Man]

I may not have free time for the next month or so, so I thought I'd go ahead and release my pretty much fully functional A* pathfinding code.

This release is a fully self contained A* pathfinding system for use with virtually any actor in EDuke32. This code will attempt to build a shortest path from an actor to a specific target - currently it only targets the player. This code only builds the path, actual pathfinding will need to be done by actors themselves.

I am planning on writing and releasing a more in-depth example AI that actually utilizes A* and not just a demo that outputs paths. I will need a bit more free time before I do that though.

Shameless copy/paste description from my site:

Quote

The A* Pathfinding project is something that I started in 2007 and have again picked back up recently in my spare time. It is an attempt at bringing modern pathfinding into the aging engine. The original version used map placed waypoints to build navigation paths, as well as hint waypoints about the world (doorways, exposed positions, cover from attacks, so on) as well as various interactive elements (AI usable buttons, doors, etc.)

The new version that I am currently developing builds a node graph from the map itself. It also uses more updated functionality in the EDuke32 engine to make itself much more versatile. Node graphs are automatically built on map load and saved on disk to reduce map loading times.

Download
A* Pathfinding and Nodegraph code
Original 2007 code • Written circa 2007. Unfortunately the game art is missing, as are all example maps. Posted here for historical purposes only.

Feel free to post any questions, I'll be happy to answer what I can.

EDIT
I just realized there may be an issue with node graph building. In the root directory of wherever you are executing the code from (either the root eduke32.exe directory, or a custom game directory), you need to create a "nodegraph" folder before it will save them.

[Jblade]

I was looking forward to this release, I'll grab it and take a look around. nice work!

[zykov eddy]

So, how does it work? I don't see any differences. I only found a bunch of red medkits on the street, which you can even pick up.

[Jblade]

zykov eddy, on 25 July 2012 - 06:57 AM, said:

So, how does it work? I don't see any differences. I only found a bunch of red medkits on the street, which you can even pick up.

The point of it is an advanced waypoint system, it's not plugged into the enemies or anything like that. The point of it is to take it, see how it's done, and use it in your own projects. If you read up on the A* waypoint system you'll understand that this is what modern games use. Using this waypoint system you can code enemies who actually navigate the level finding the player rather than the way it is now where they randomly walk in the player's direction.

[Reaper_Man]

Yeah this really isn't a user-end release, it's for the benefit of other developers. If you aren't a programmer then unfortunately this release won't be very interesting to you. As I said in my post, the included enemy edits are only a demo to show off what A* is doing, I haven't had the chance to make a functional demo/example yet. Even when I do get a chance to write a more in-depth example, the changes are still going to be under the hood. Pathfinding is great, but it's not an in-your-face feature like, say, the features in Duke Plus.

I'd highly recommend reading the (many) lines of comments in the code, especially astar.con and nodegraph.con. I explain everything in detail with what is going on. Also you should check the top of state troopcode in liztroop.con, that's where I added the changes to them.

From the readme in case you haven't read it:

Quote

It is beyond the scope of this readme to explain A* in depth. For more
information regarding A* and a boring Wikipedia article, check out these sites:

http://www.policyalm...tarTutorial.htm
http://theory.stanfo...ameProgramming/
http://en.wikipedia....earch_algorithm

EDIT
I just realized there may be an issue with node graph building. In the root directory of wherever you are executing the code from (either the root eduke32.exe directory, or a custom game directory), you need to create a "nodegraph" folder before it will save them.

[Reaper_Man]

Okay so I'm climbing back on the horse. Back from my vacation, recovered from surgery. Ready to make something useful out of this. Will document progress I make.

In the meantime, anyone want to throw together some testing maps? Really I just need some small basic maze type maps, slopes and stairs/other sector height increases would be great. No doors or other crazyness just yet.

[Reaper_Man]

First things first, I'm working on refining the node graph stuff. I'm adding a graph density control actor, so that a mapper can define a more coarse or more fine grid on a map-by-map basis. Very generally speaking, maps with extensive "indoor" areas (corridors, rooms, so on) would work better with a finer graph. Whereas outdoor maps, or maps where there is a large amount of open space, would work best and be much faster with a less dense graph. But since there are exceptions to every rule, I'm also adding a hint actor which will define it's own graph density in a radius around itself. So your giant outdoor map can have a coarse grid, and if you have buildings scattered around, you can define regions of high graph density in those so that the AI can properly navigate any tight hallways and rooms inside them. I'm also finishing adding the node "scoring", so that the AI will attempt to navigate around hazardous sectors (slime, lava, probably water too) as well as hazardous actors (fire, explosive barrels, etc.).

None of this is really directly related to the AI project so I'll probably update my A* package with this once I'm finished with it. I'm also probably going to go through the A* code itself and make some cleanups and refinements before I move on to the actual AI stuff. So I should have an update to the A* files, in case anyone is using them currently. None of the state names will change so in theory you won't have to make any changes to your code.

When I move on to the actual AI stuff, I shouldn't have to make any changes to node or A* code, the idea being that my nodegraph/A* code and actor AI code can be used independently of one another. As stated before, the A* code is completely stand alone. It only returns a path from A to B; what A and B actually are, and what an actor does with the path that's returned, should be completely up the individual actor code.

[Reaper_Man]

So there may possibly be a bug here, either with A* or with changes made to engine.c at some point in 2013. I'm looking into it now, but if anyone is using this and has weird problems with large concave shaped sectors, speak up.

[icecoldduke]

Great work : ).

[Hendricks266]

Reaper_Man, on 25 November 2015 - 11:10 AM, said:

So there may possibly be a bug here, either with A* or with changes made to engine.c at some point in 2013.

Jaap asked me about it on IRC, and when I tested his hypothesis by reverting r3898, one test of his test cases started working but the other was still broken, leading me to believe the problem is with the A* code.

[Reaper_Man]

Hendricks266, on 26 November 2015 - 08:43 AM, said:

Jaap asked me about it on IRC, and when I tested his hypothesis by reverting r3898, one test of his test cases started working but the other was still broken, leading me to believe the problem is with the A* code.

I am definitely not ruling out bugs in A*. But what strikes me as odd is that a path will work pre-r3898 and fail post-r3898.

There seems to be 2 issues here - node building, and path building. The node building stuff seems to be affected by the changes in r3898. My guess is that large, concave shaped sectors are causing issues. The map Jaap and I are testing on would fail when it was one large sector, but when I had him break it up into smaller sub sectors, the cases that failed would now succeed. This is in the current engine release.

Debugging code in A* says there is 772 nodes generated before r3898, and after r3898 there are 817. In NODEGRAPH.CON where the list of nodes is built, it builds a grid of X/Y points and discards any that (among other things) are in the void:

		// Now we build the list of valid X/Y points and store them, dumping
		// any invalid nodes. This will be our actual node graph
		setvar NODETEMP 0

		// Loop through X...
		setvarvar NODEPOSX MINX
		whilevarvarn NODEPOSX MAXX
		{
			// ... Then loop through Y...
			setvarvar NODEPOSY MINY
			whilevarvarn NODEPOSY MAXY
			{
				// ... And if the position is not in the void, let's add it to our node graph
				updatesector NODEPOSX NODEPOSY NODESECT
				ifvarn NODESECT -1
				{

Right now I am having Jaap test something to verify if nodes that previously were discarded are now being considered by the engine to be in a sector but still in the void, which would cause the problems we're seeing. But it seems that "updatesector" may be returning incorrect results for invalid X/Y points in the void.

Again, I am not ruling out a bug in A* because there are cases that fail in both versions of the engine, so that's something I am looking into. But the path building bugs are not related to the node graph bugs and "updatesector" returning different results.

[Danukem]

This won't help solve the current mystery, but, would it make sense to specify a z coordinate as well and use updatesectorz instead of updatesector? It could eliminate some false positives.

[Reaper_Man]

Trooper Dan, on 26 November 2015 - 01:34 PM, said:

This won't help solve the current mystery, but, would it make sense to specify a z coordinate as well and use updatesectorz instead of updatesector? It could eliminate some false positives.

Does updatesectorz return true in cases where updatesector wouldn't?

The simplest reason is that it doesn't need to worry about sector heights at that point in the code. The idea is that it will go through all valid X and Y locations and discard any that are in the void, so you have a list of locations that are potentially valid. I don't have a Z position to work from, the closest thing I could do is pull the floor height at that position. There are some checks later on that invalidate some points based on Z space - points where the floor and ceiling are the same height, points where the floor and ceiling are parallax (like the space sectors in E2 maps), etc. - but I tried to make the node building as neutral as possible when determining what possible points are and are not valid.

The pathfinding code will worry about Z position and if adjacent nodes are "too high" to traverse. Some enemies this isn't an issue for - a Liztroop can turn on his jetpack to fly up to it - so I don't want to have to have multiple versions of the A* routine when it's not necessary.

[Danukem]

Reaper_Man, on 26 November 2015 - 02:38 PM, said:

Does updatesectorz return true in cases where updatesector wouldn't?

The opposite, I think: updatesectorz will return -1 in some cases where updatesector returns a sector number. But I can understand why you don't want to bother checking for z at that point in the code.

[Reaper_Man]

That's something to test at least. I'd just have it grab the Z position of the floor at a given X/Y position, which I would think would produce the same results, but it's worth trying.

Question (to anyone): Do actors spawned in the void during gameplay automatically get removed? My node debugging code spawns SIXPAK actors at all points in the graph, and then I used dndebug to export the map - but there aren't any that are outside the boundaries like I would have expected. So either it actually is not spawning them in the void, or the game is removing them for me.

That said, I did notice this at one of the points where the pathfinding does fail:



These are node graph points exactly on the walls. Pre-r3898 this would fail, and one of the changes in that revision make points on a wall be considered "inside". I assume this change affects how cansee works since the code uses that when building it's open list of nodes. It should follow points along the wall, and pre-r3898 it does do that. But it seems that the points on the wall are seeing through the walls in the A* code when it's building next nodes.

[Danukem]

Reaper_Man, on 26 November 2015 - 04:13 PM, said:

Question (to anyone): Do actors spawned in the void during gameplay automatically get removed?

I know they used to persist -- I don't know if they do any more. If someone added a check for that, then the natural place to do it would be during the spawn itself (i.e. maybe a check is preventing sprites from being spawned in the first place if the destination is void).

Reaper_Man, on 26 November 2015 - 04:13 PM, said:

But it seems that the points on the wall are seeing through the walls in the A* code when it's building next nodes.

That's interesting and I hope you can definitively confirm it one way or another. I am pretty sure I have had problems with enemies trying to fire at the player through walls, even when using an "ifcansee" check -- could be related.

[Mblackwell]

I think I've only had that problem with maskwalls or sprites still returning true ifcanshoot but who knows. That definitely doesn't sound right however.

A question though (more of an aside): Are you using both canseespr and cansee? The level of precision is slightly different (or seems to be) since a sprite may not be visible even if the point on the map is, and vice versa. In some code (unrelated to AI) I ended up stacking the two as a failsafe for some edge cases.

[Reaper_Man]

Mblackwell, on 26 November 2015 - 07:20 PM, said:

I think I've only had that problem with maskwalls or sprites still returning true ifcanshoot but who knows. That definitely doesn't sound right however.

A question though (more of an aside): Are you using both canseespr and cansee? The level of precision is slightly different (or seems to be) since a sprite may not be visible even if the point on the map is, and vice versa. In some code (unrelated to AI) I ended up stacking the two as a failsafe for some edge cases.

No, because I'm not actually comparing 2 sprites. I have debug code that spawns SIXPAK actors at the coordinates on the graph, but those are just for debugging purposes - the actual graph is literally just a list of X/Y positions.

Technically I shouldn't need to use any sort of line-of-sight checks because everything is already setup on a grid and A* looks for nearest adjacent nodes, but it's a failsafe because of moving sectors and other runtime modifications to the actual map.

Also without going off on a huge AI theory tangent, I'm trying to keep the actual pathfinding from making any real decisions between if an actor using A* should or should not ignore a destination. There may be cases where one enemy can path find between 2 points that another enemy couldn't, again using the Liztroop jetpack example. It's up to the individual enemies to decide how to act on a given path they're given.

[Jaap]

Oh I would like to add one thing.

Just cutting the map in smaller sections did not make certain cases work. Only changing the sector in which the path broke did.

Not sure if the other case where it doesn't work it a bug in A*, the eduke code or if I just broke the map. (I am good at making maps that seem okay but are actually horribly broken).

[Reaper_Man]

Jaap, on 29 November 2015 - 02:17 PM, said:

Oh I would like to add one thing.

Just cutting the map in smaller sections did not make certain cases work. Only changing the sector in which the path broke did.

Not sure if the other case where it doesn't work it a bug in A*, the eduke code or if I just broke the map. (I am good at making maps that seem okay but are actually horribly broken).

In that case it isn't the size / shape of the sector, it's nodes lying exactly on the wall that are allowing it to see through the wall.

Is there a way to detect if an X/Y position is *exactly* on a wall? If so I can simply throw out those nodes.

[Danukem]

Reaper_Man, on 30 November 2015 - 10:17 AM, said:

Is there a way to detect if an X/Y position is *exactly* on a wall? If so I can simply throw out those nodes.

OK this is almost certainly not good enough, but it gave me a chuckle. Here is the source code for the "ifawayfromwall" CON command:

case CON_IFAWAYFROMWALL:
        {
            int16_t s1 = vm.g_sp->sectnum;
            tw = 0;
#define IFAWAYDIST 108

            updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
            if (s1 == vm.g_sp->sectnum)
            {
                updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                if (s1 == vm.g_sp->sectnum)
                {
                    updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                    if (s1 == vm.g_sp->sectnum)
                    {
                        updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
                        if (s1 == vm.g_sp->sectnum)
                            tw = 1;
                    }
                }
            }
            VM_CONDITIONAL(tw);
        }
        continue;

So all it's doing is checking whether the sector changes if you move the x and y values by 108 plus or minus. Of course that will count any wall, including red walls, whereas you are probably more interested in white walls (although red walls matter too if the floor or ceiling height is different). By reducing it to a much smaller distance (e.g. 32 instead of 108), you could get a more accurate version, but it will still kind of suck.

[Jaap]

Trooper Dan, on 30 November 2015 - 11:07 AM, said:

OK this is almost certainly not good enough, but it gave me a chuckle. Here is the source code for the "ifawayfromwall" CON command:

case CON_IFAWAYFROMWALL:
        {
            int16_t s1 = vm.g_sp->sectnum;
            tw = 0;
#define IFAWAYDIST 108

            updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
            if (s1 == vm.g_sp->sectnum)
            {
                updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                if (s1 == vm.g_sp->sectnum)
                {
                    updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                    if (s1 == vm.g_sp->sectnum)
                    {
                        updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
                        if (s1 == vm.g_sp->sectnum)
                            tw = 1;
                    }
                }
            }
            VM_CONDITIONAL(tw);
        }
        continue;

So all it's doing is checking whether the sector changes if you move the x and y values by 108 plus or minus. Of course that will count any wall, including red walls, whereas you are probably more interested in white walls (although red walls matter too if the floor or ceiling height is different). By reducing it to a much smaller distance (e.g. 32 instead of 108), you could get a more accurate version, but it will still kind of suck.

It sure is easier to implement than what I had in mind (looping through all the walls of the sector the node is in, checking if the node is between the wall.x/y and wall.p2.x/y and then using getangle to compare angles).

[Jaap]

I guess I got it working paths are generated and 90% of them are okay now. Not sure why but some times I get a path that goes into walls, (maybe I sorted the result path wrongly).

In the gif below you can see the actor (the nuke symbol) following a path (each blue spot is a node), the red earth thing(in the right top corner) is the final destination and the moving red square is the node the actor is currently trying to get to.

Attached thumbnail(s)

• 

[Reaper_Man]

How is it trying to get from Node 1 to Node 2 exactly? The correct way would be to have the actor iterate through the node path that astar returns. Or are you still placing arbitrary "waypoints" and using those instead of the node graph?

[Jaap]

Reaper_Man, on 02 December 2015 - 08:53 AM, said:

How is it trying to get from Node 1 to Node 2 exactly? The correct way would be to have the actor iterate through the node path that astar returns. Or are you still placing arbitrary "waypoints" and using those instead of the node graph?

I am using the result of astar. The blue balls are sprites I spawn on in stead of the sixpak's used in your liztroop actor. I tried using the result as is but that resulted in backwards paths. But that fixed it only for a part of the results. So I tried sorting the path based on the value. That made it work for 90% of the cases but in some instances the path is just very odd.

Not sure why :S

[Reaper_Man]

It has come to my attention that the implementation of A* in this release is, basically, totally wrong and doesn't work under many conditions.

I've refactored the entire code base and it now works with much better results, greater performance, and far fewer edge cases where it will fail out entirely. In particular, deep concave mazes would cause it to hit a failsafe, which is no longer necessary.

I am doing some code cleanup, and writing an example AI agent that uses this to traverse paths, and will be releasing the update in the next few days. In the meantime, here's some examples of A* traversing 3 different kinds of mazes:

[Jaap]

Reaper_Man, on 10 December 2020 - 08:56 AM, said:

It has come to my attention that the implementation of A* in this release is, basically, totally wrong and doesn't work under many conditions.

I've refactored the entire code base and it now works with much better results, greater performance, and far fewer edge cases where it will fail out entirely. In particular, deep concave mazes would cause it to hit a failsafe, which is no longer necessary.

I am doing some code cleanup, and writing an example AI agent that uses this to traverse paths, and will be releasing the update in the next few days. In the meantime, here's some examples of A* traversing 3 different kinds of mazes:

Duke voice: Hail to the reaper man! Good to see you back at it! I've made my own path finding version but I am very interested in yours vs mine (you can see a crappy preview of mine here).

[Micky C]

Nice! Does it handle things like pits and water that it needs to walk around?

[Reaper_Man]

Micky C, on 10 December 2020 - 12:39 PM, said:

Nice! Does it handle things like pits and water that it needs to walk around?

Yup, in a few ways.

For one, the navigation node graph ignores certain floor textures altogether (IE things like parallaxed floors for special effects), and other textures can have penalties assigned to them. So if you wanted AI to avoid floors with slime or lava, the path would find it more "expensive" to cross it and would try to find a way around. Things like bottomless pits are handled by some line-of-sight checks, so maps will need to be somewhat designed with the pathfinding in mind. There's also some special actors you can place to add penalty "zones" similar to floors, so you could place some hint nodes to make pits have a high penalty to them.

[Reaper_Man]

https://gfycat.com/h...ecommabutterfly

Checking over the obstacle avoidance penalties. AIs can be told to avoid terrain hazards (things like damaging floors) or placed objects, like explosive barrels. Or this system can generally be used to make AI prefer certain paths over others, IE walking through a jungle and following a trail, rather than going in a straight line. Hint actors can be written to influence the penalty on map load as well, so mappers can place actors to finely tune how the navigation is handled on their map.