24 replies to this topic

[JohnnyLightwave]

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]

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]

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.

[JohnnyLightwave]

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.

[amrazek111]

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/