automatic pathfinding

by concray on 05/27/2013 23:19, 6 messages, last message: 06/21/2013 07:40, 1508 views, last view: 04/24/2024 22:31

this is more a topic of discussion/half baked idea of mine, but i think it is interesting:
i stumbled upon recast, you give it a mesh and it automatically makes you a graph for pathfinding.
It works like this:
it makes a voxel world out of your mesh and than a "slab world"* out of that. Since we already have the voxel world it should be easy to make slabs out that:
traverse the tree until you find an empty cube, add a slab of that size to all cells of the 2d array that the cube encompasses. I tried this once but it basically ended in failure/gave the program a heart attack.
Basic questions: if i have a world of size 12, i would need an array of 2^12 length. If i wanted a bigger resolution i'd look at the definition of the cube, where the endpoints are, and go from there.
Does anyone know how to calculate from the cube size and endpoints the world coordinates? And how big is the smallest cube?

(just as a note, i know this is all probably out of my depth and biting of more than i can chew but i just like playing around with the source)

*by slab world i mean: a 2d array where the empty areas of the z-dimension (height) are defined by a startingpoint and an endpoint.

   Board Index   

#1: ..

by Q009 on 05/28/2013 08:30

The smallest cube is 2^0 which 1

reply to this message

#2: ..

by concray on 05/29/2013 02:54

ah great, i just assumed for gravity you use something like 9.81 and you scale the cubes accordingly, but than it's the other way around.

reply to this message

#3: ..

by Papriko on 05/29/2013 11:18

// physics.cpp: no physics books were hurt nor consulted in the construction of this code.
// All physics computations and constants were invented on the fly and simply tweaked until
// they "felt right", and have no basis in reality. Collision detection is simplistic but
// very robust (uses discrete steps at fixed fps).

reply to this message

#4: ..

by Meigus on 05/31/2013 07:40

Why even go that far? I'd try something like shooting arrows down from the sky, until it hits a traversable space before colliding with something (don't want any navmaps in places bots can't go). Then use a naive traveling salesman, with maybe a collision test which just involves lobbing something from one arrow to the other, and seeing if anything collides in-between. If it doesn't collide, then that path should work, and make it so maybe there's a max of 3 or 4 paths to each node, then call it a day. "Lobbing" would avoid trying to find a straight path over bumpy hills.

This method would be really naive, and wouldn't work right for caves or anything, but it'd be a good 'blobby' path, and then the bots just decide to use more erratic jumping and attacking when they see someone or get within range of an objective.

A better method might be to use ants. Drop AI on the map, either manually or from the spawn points. Have them go about brute-forcing the game, and dropping the virtual pheromones where they go (could even represent them visually while watching the bots). After a bunch of pellets are on the ground, pick a level of sensitivity, determined by pellets with radius of a pellet (simple enough to do if say 24 bots have 50-100 pellets, with the data stored in an array with maybe team-value to have team-biased paths) AND maybe a min/max to nearby pellets, so a min would determine a "this path is useless" and the max would prevent a bottleneck by trying to keep "too perfect" paths from happening.

If the map turns out to be too clustered, you could set "ignore dropping pellets within this point" to make the bots spread the pellets out more. After a while, you could look at the major nav-paths, and either manually connect them, or have them automatically connect, then make bots test all paths. If they can't go from one point to another, you can determine it's a broken path, and trim those. You'd end up with a rough map of optimal layout, where the AI won't be sitting there trying to climb up a tall hill.

reply to this message

#5: Re: ..

by Papriko on 05/31/2013 11:41, refers to #4

Waypoints with settings?
Right now waypoints are added to the map by using /dropwaypoints 1 and /showwaypoints 1 and then running over the map till you get a nice blue carpet.

This arrow-from-the-sky-story may make problems too. You had to mind clip too, since is used a lot to create better floors or to limit certain paths. The annoying thing is that most maps are covered with a kind of clip-dome to prevent jumping out. How do you want to determine if it's just the clip-dome or clip which is important for your path?
Sometimes it even may be both. On the map aqueduct or whatever it is spelled, you can teleport to such a tiny island which looks as if it has a smooth transition to the border of the map.
Yet you can not enter it due to it being part of the clip-domes wall.

reply to this message

#6: posting

by Naveed123 on 06/21/2013 07:40

hi this is very very nice and wonderful post.

reply to this message

   Board Index