View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Pathfinding with nodes... finding the first node.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

24 replies to this topic

### #21JohnnyLightwave  Members

Posted 05 December 2012 - 08:06 AM

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.

### #22amrazek111  Members

Posted 07 December 2012 - 09:08 PM

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?

### #23BCullis  Members

Posted 08 December 2012 - 11:35 AM

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.

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)

### #24JohnnyLightwave  Members

Posted 09 December 2012 - 06:07 PM

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.

Edited by JohnnyLightwave, 09 December 2012 - 06:08 PM.

### #25amrazek111  Members

Posted 09 December 2012 - 06:51 PM

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/

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.