Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 18 Nov 2009
Offline Last Active Nov 05 2013 01:00 AM

Posts I've Made

In Topic: Complicated visibility determination?

11 November 2011 - 07:02 PM

It needs to be independent of the location of enemies, which are unknown to the AI. The idea is to figure out the intersections of areas where every node in the area is visible to every other node in the area.

So don't think of it like pathfinding as in many games. Once I identify the locations of note I know what behaviors I want and how to achieve them.

Right now I just have a bit array that shows if location is walkable or not, plus they are in regions but the regions are not convex any more due to some changes I made recently. I'm thinking to add a link to some data structure that says what is visible from where. The important part though is to find the transitions, like I explained.

I'm looking into dynamic connectivity structures like link-cut trees but I don't think it needs to be dynamically updatable necessarily. But if there's a freely available implementation of that and it works like I think maybe that should at least take care of building the structure itself which would be nice.

For similar games a lot of time it's tile based. So it's obvious you have a door tile or window tile and that makes the AI easy to deal with for that spot. You know what the entrances and exits are pretty naturally. The problem is I don't really limit things like this, because it doesn't make as much sense and also I want to avoid having to hand place AI markers or having maps that are tile based (though in 3D) and squarish maps or maps that consist of tons of corridors.

In Topic: Complicated visibility determination?

10 November 2011 - 10:03 PM

I looked into it a little more. I don't think I really need to make influence maps person by person or that it would help me.

For one I don't want to find cover from a specific character's current location, it's more to realize what areas are "danger" areas in general. So if stepping outside a building or into a corridor intersection, the AI needs to be able to realize it might be walking into a hostile location.

So I really need a data structure on top of the walkable node areas where I can query if 2 nodes are visible to each other that returns a fast result. But generating that out in brute force could be quite time consuming and require a lot of space. There's something like 100k nodes in a typical map I'm using.

Now I'm trying to think if there's some way to partition this into larger spaces then connect those or something.

In Topic: Complicated visibility determination?

05 November 2011 - 11:38 PM

Thanks wodin, that gives me something to work with. I was hoping there was some easier way to do things but maybe that's not possible.

In Topic: Best way to "shrink" a navigation mesh to account for npc radius

05 November 2011 - 12:12 AM

I don't use detour but what I do is keep a list of visited nodes then I make a new graph from all the visited nodes but subdivide it to be smaller.

In Topic: What heuristic should i use for A* ?

04 November 2011 - 11:49 PM

When I did the overestimating it made things much faster, but while most paths were fine when I had irregular geometry it could do strange things like hug a wall that was curving AROUND the goal.

For heuristing I was wondering if there's something that takes directionality into account more as I still don't always get the most obvious path for straight line.

Directionality is taken into account when you compare the other values of the potential squares you want to search next. If you move away from the goal, your cost goes up. If you move toward, the cost goes down. All the heuristic represents is a starting point from which to compare the total distances of your future selections. And for distance, no direction is needed.

Yeah but there's multiple paths that might be optimal but some are better than others. The problem I get is that I usually get a path that has one krink in it and looks odd and deviates too much from the straight line path.

Then I do something similar to the "funnel" algorithm to get a better path but it would be nice to start with something closer to what I want.