Pathfinding with Chipmunk

By Basic Date 2010-10-12 18:29

I don't really see the connection between path-finding and a physics engine. And a side on 2D physics engine will generally be move left or move right.

By RavensKrag Date 2010-10-13 00:41

That's why I said I was using the Chipmunk space to represent a horizontal plane, rather than the vertical plane often used in side-scrollers. Also, the connection is that the physics engine already holds the positions for where everything is, so I wouldn't want a path-finding algorithm that created some sort of bitmap as an intermediary stage. I'm not even sure if a path-finding algorithm like that exists, but there definitely is a collision detection algorithm like that.

Here's an example of path-finding using the glaze physics engine
http://jaketastic.com/blog/heuristic-uninformed-realtime-adaptive-2d-pathfinding-using-ray-casting/
I'm pretty sure similar logic will carry over into Chipmunk.

However, as I said before, I just want to see if anyone has already done this and would let me use their code before I go ahead and do it myself. I'm pretty new to path-finding, so I figured if someone had already done something it would probably be a lot better than my solution.

By Basic Date 2010-10-13 17:10

ah I saw horizontal and thought side scrolling. although chipmunk not so hot at top down stuff, I tried faking a top down racing game in chipmunk, it kinda worked but not really nicely.

I've only done grid based pathfinding.

Heres an easy grid based pathfinding tutorial.
http://www.gamedev.net/reference/programming/features/astar/

Implementing A grid based pathfinding with chipmunk isn't any harder than not. Just the object coords are held in chipmunk instead.

By RavensKrag Date 2010-10-14 06:07 Edited 2010-10-14 06:36

I read that tutorial already, and while helpful, I'm trying to make a game that is not restricted to grid-based locations. From the link I posted, it seems as if a modified version of A* can be used in a non-grid-based space by substituting the grid tiles with waypoints. This comes from the fact that A* really only cares about the pathways between the tiles, and not the tiles themselves per say. Or, put another way, it's the edges which are important, not the nodes.

I'm explaining this really badly though ^_^;

All in all, thanks for trying to help anyway.

That top-down racer sounds kinda cool. It's too bad Chipmunk didn't work out for that though, though I suppose I kinda see why. One would have thought it'd just be the same as the Chipmunk integration demo in terms of getting things to move and such. That's basically what I did for this game, except I assumed the units used by Chipmunk were meters instead of pixels. Ah, but I'm getting off topic...

By Spooner Date 2010-10-14 12:47 Edited 2010-10-14 12:49

I used an overhead 2D chipmunk in the last version of my Alpha Channel game (my LD18 entry, though I didn't re-release the Chipmunk version). The only difference between overhead and side-on usage of a physics engine is whether you apply gravity to it, so I don't see that Chipmunk is inappropriate for any system in which 2D planes are used (you can even have 2.5D since you can give items a Z attribute and only things on the same Z will collide).

And yes, A* works on any graph, whether it is a grid or another shape. I don't think the ray-tracing system is really workable - it would work, I suppose, but I can't see that it would be less complex or more efficient than A*.

By RavensKrag Date 2010-10-14 20:00

I am actually using Chipmunk for what you could call a 2.5D environment, as I also have a z variable tacked on to control height.

However, is it possible to use A* for a dynamic environment? By this I mean, if you had moving barriers, would it still work? From what little I have seen, A* does not seem to work in that scenario.

The ray-tracing system is certainly not any less complex, but I was considering it in order to be able to get pathfinding in a dynamic environment.

Side note: You could always use gravity in this scenario to simulate a strong wind in one direction or something.

By Spooner Date 2010-10-14 20:16

A* would need to be recalculated each time the environment changed, unless it ignored barriers (that is, the AI would wait at the barrier until it opened, rather than seeking alternative, longer paths when its way was blocked; alternatively a blocked route could just be given a higher cost rather than breaking the edge, to prevent the AI from running all the way around the map to avoid the blockage). It has to be recalculated each time the target moves anyway, to see if there are shorter paths opened up, so I don't see recalculation as a great problem.

The choice is also a lot about the omniscience of the AI. If you use A* (and, say, add cost for a temporarily blocked route) then you assume the AI has full knowledge of the position of the player, the barriers and knows the map implicitly. In a ray-tracing system, you are simulating the AI having no knowledge at all, beyond what it can see, which is probably not what you want in a game (rather than a simulation).

By RavensKrag Date 2010-10-15 07:55

I was thinking of using a ray-tracing system for wide open spaces and field locations, where both you and the AI would have little knowledge of the terran. However, I think it would be good it integrate A* as well in bases or fortresses or what-have-you controlled by AI opponents. The rationale being that the AI should have a good sense of the terrain in an area controlled by NPCs.

However, I want the AI to attempt to guess where the player is going, based on what it has "seen" or "heard" or something similar, rather than by being omniscient and knowing exactly where the player is. Any ideas on how to do this? Basically, I would like the AI to be able to figure out, "oh he's going down that corridor, so I'll go this way and flank him." I suppose this bleeds over into other areas of AI though.

By Spooner Date 2010-10-15 10:09

I don't really have much experience of implementing this sort of AI, so I'm not sure what level of help I can give. However, I will suggest that AI in games that don't cheat _to_some_degree_ generally appear stupid (or grind the game to a snail's pace with excessive calculations).

For example, the AI in Arma are not scripted and work off the realistic information they have available in the very open terrain. They often appear extremely dumb compared to AI in other FPS games, which usually use very restrictive maps with scripted behaviour. However, they are very versatile and can manage to do _something_ being dropped into absolutely any map in any situation. It is swings and roundabouts...

By RavensKrag Date 2010-10-16 00:56

From what little I know of game programming, I would have to agree with you. Game programming seems to be about ways to fake stuff really well imo.

Hmm, that's rather interesting, I'll have to take that into consideration, thanks a lot.

By Maytsh Date 2010-10-15 13:31

> Basically, I would like the AI to be able to figure out, "oh he's going down that corridor, so I'll go this way and flank him."

Leading to the player quickly jumping into and out of long corridors to make the AI take detours? Often, when you try to make the AI smart, it just ends up looking even more stupid once the player figures out the rules... :)

By RavensKrag Date 2010-10-16 00:54 Edited 2010-10-16 01:05

I would make it so the AI would go look in a location based on where the player was last seen, not the actual location of the player. That should mitigate this problem.

Basically, what I want is something like how the AI is designed in Splinter Cell: Conviction, where the AI will look for you where you were last spotted. However, it would be modified slightly to store you velocity and position when you are spotted, so it can try to guess where you are headed.