Back to General and Gameplay Programming

Pathfinding with nodes... finding the first node.

John Raptis · 2012-12-10T00:51:34

Hi all, I've implemented an a* node pathfinder. Everything works great, except one thing: finding a node to start at. In order for a node to be acceptable, there's a "clear path" test that I run-- as in, can I draw a straight line to this node and not encounter any obstacles. My problem is, the "clear path" test, while not cpu-intensive, is *too* CPU intensive to run through every single node. I'm trying to figure out a good way to narrow down the nodes I am going to test. My first thought was to maintain a grid and a set of pointers to possible nodes, but I have a problem in that a node might be accessible from one section of a grid square, but not another-- or worse, a node might actually be accessible from the grid square, but not from any of the arbitrary points I choose to test. I've considered a polygon mesh with pointers to nodes, but since my node system has to autogenerate (user created levels) from a field of lines and circles, I haven't been able to come up with any sensible algorthm to generate a polygon mesh that works every time. A friend suggested to me that I give each node a radius and preprocess them to see which one can be accessed from arbitrary points on the screen-- and then if the player is within the radius of the node, it can do the clear site. This is a good solution, but because the game has a lot of open areas, the nodes tend to inflate to the point where only a few get culled out, and it's almost no help at all. Does anyone have a creative solution for narrowing down the node tests?

General and Gameplay Programming Programming

Started by JohnRaptis November 23, 2012 10:41 PM

23 comments, last by amrazek111 11 years, 4 months ago

JohnRaptis

188

Author

December 05, 2012 02:06 PM

Hi Jedillama, thanks for the psuedo, but I already have an A* routine that navigates nodes. The issue is finding a node to start with, from a character standing at an arbitrary point, likely not on a node.

amrazek111

1,080

December 08, 2012 03:08 AM

Currently, the game just works by testing all nodes-- simply "draw line from node 1 to player, yes no? Draw line from node 2 to player, yes no?" With only a few nodes, works fine, but as the numbers get up there, doing the line test gets nasty.

Wait, do you mean you test each and every one of the (potentially) 10-20k nodes until you get a hit? Don't you sort them using some kind of spatial partitioning algorithm?

BCullis

1,955

December 08, 2012 05:35 PM

[quote name='BCullis' timestamp='1354632595' post='5007088']
Step 3: If no best option was generated, expand "potentials" list to neighboring grid squares, repeat.

No, this would be a correct way to do it. The issue would be that in order to satisfy step 3, I would have to have a potentially huge list of potentials. Like, take a look at this:
http://i.imgur.com/vGWAE.jpg

(Square would be a member of the grid set, circle is a node, red lines are impassible obstacle lines)

The yellow lines would be my initial set. The green line is valid, but when it actually gets tested would be indetermined-- it might be 50 iterations in.

Meanwhile, any grid square that CAN'T reach that node has to go through *all* the possible iterations. This becomes a speed issue.

I think I'm going to go another direction and see if I can't make a floodfill/navmesh out of the area. Some of my navmesh polygons would be pretty small, especially in tight places, but I haven't read anywhere that that's a problem.
[/quote]

Okay, now I see the issue. I wasn't able to view the image link from my work PC.

Are your pathfinding nodes actually squares? I thought they were a point list. When I mentioned a grid-based partitioning method, I intended for it to be a grid-like partitioning of the gamespace, strictly to partition the list of navigation nodes into "locals" and "others" when in any particular spot on the board. This would let you only straight-line test against local nodes, culling some 80% of your candidate list. You could grow it to neighbors if necessary.

I don't see what the corners and midpoint are supposed to calculate, unless you are using grid-spaces as actual navigation nodes.

Hazard Pay :: FPS/RTS in SharpDX (gathering dust, retained for... historical purposes)
DeviantArt :: Because right-brain needs love too (also pretty neglected these days)

JohnRaptis

188

Author

December 10, 2012 12:07 AM

Wait, do you mean you test each and every one of the (potentially) 10-20k nodes until you get a hit? Don't you sort them using some kind of spatial partitioning algorithm?

Coming up with a sorting algo that is efficient in both speed (has to generate quickly for user generated levels, can't leave them hanging while sorting for minutes) and catching all cases and memory is the problem.

I have dozens of different algos that are too slow, destroy memory, or work in 95-99% of cases.

amrazek111

1,080

December 10, 2012 12:51 AM

I had sort of a similar problem some time ago; I needed to do efficient collision detection on a small subset of moving objects (with my upper target being around 6k). Maybe some of the suggestions proposed then would help you now: http://www.gamedev.n...h-many-objects/

Pathfinding with nodes... finding the first node.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Pathfinding with nodes... finding the first node.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines