AI Pathfinding method

[DarkLightHitomi]

I am building a general AI for controlling a unit in a simulated environment, like a game (and will be testing it in a rogue-like).

The thing is, I am aiming for the AI to have the same limits as a player.

For example, in this case, the AI can only pathfind according to the parts of the map it has seen and knows.

I figured I would share my planned method and get some feedback.

The core concept revolves around the AI defining lines (that can't be crossed or have a cost to cross).

To test whether two lines cross (for pathfinding one line would be from current position to destination or waypoint), find the distance on both X and Y from each point (either end of the line and the destination), then take the ratio of X to Y for each point to get a pseudo angle. If both line points are on the same side (both larger, or both smaller ratios, neither the same as) than the destination ratio, then the line doesn't impede a straight course to the destination.

Using this, as the AI discovers obstacles, it remembers them as line segments and if a line segment is in between it and where it wants to go, then it makes a waypoint just past the line segment.

As it does so, it remembers the waypoints, start and destination, tying them together in order to remember a route.

Both routes and multi-segment obstacles can be refined by comparing three points along the line, if the middle point is close enough to a straight line between the two on either side, it can be forgotten. The segments should kept from getting too long though, otherwise a large circle could be refined into a small line.

Anybody got feedback, or questions?

[jonnin]

If it is a competitor for the human, you don't want to be predictable, which the optimal path would be, but if you go another route than the optimal you can ambush someone, for example, in a FPS.

this approach of yours is a graph-theory approach and is likely to become extremely difficult to get working, have tons of data, and perform poorly for larger maps or over time as more data is added. Its doable, but you are basically doing some variation of the travelling salesman problem. Make sure you understand what you are getting into here, and the potential snares.

[DarkLightHitomi]

I expect the growing data issue, but my hope is to optimize that at least somewhat, hence lines rather than mapping (though using polygons in certain cases could be helpful. The lines would refine themselves when the same area is gone over multiple times, rather than simply building new ones. Also, data that is older or from areas that are rarely traveled would be forgotten or overly simplified beyond general usefulness to keep the data size down (the latter would mostly be marking that possible routes exist there, or don't)

My idea is that I might use this for gaming on large scale generated maps (where the entire map is not available, or even generated, at the same time, not even all the way to the destination), but I really want it to work for something like robots too, where it quite literally has no reference except what it encounters. Also, being able to share the info with allied units is a benefit, especially in multi unit coordination.

I admit also that the idea started when playing Starcraft and realized I could gain info about the map by sending units into the darkness and they would respond to terrain before it was discovered, and that bothered me.

The idea behind recording routes is because it can then cross link them later, share them with units that haven't been there, and use them to predict possible enemy routes.

As for setting up ambushes and stuff, how is that pathfinding?

Also, predictability and ambushes are things I'm lumping into the high level strategies building section. Much like how you can have an ai play chess, and do it well, I plan on having a high level conceptual strategy that then has lower level implementation of strategy. For example, the ai might deliberately decide to make an ambush, then using what it has learned of the map, it would set up an ambush along expected enemy routes. But then the ai would also need to consider how the opponent might attempt the same and try ways of handling that, such as alternative routes, extra companions, stealth, etc.

[DarkLightHitomi]

I don't think this is graph theory, as that comes up as being algorithms like Dijkstra's and A* which evaluate map data until the destination is found before plotting a course, where-as what I'm doing is designed to be able to actually head for an uncharted destination, and respond to new information and obstacles as they arise, and there-fore can handle moving to a destination without complete information and even without holding the entire route from start to finish.

Edit: Another difference is that the graph-theory idea has nodes with node costs for moving from one node to the next, where-as here, movable space is freeform with no defined location. It isn't moving from one node o the next that has a cost, but rather crossing a line has a cost, or a limitation/requirement (such as swimming, climbing, flying required to be passable, otherwise completely blocked).

[jonnin]

It may not be, but your initial description sounded like it. I think I see where you are going better now.

Ambushes and strategy are directly tied to pathfinding. You want to get from here to there, that has not changed, but you want to avoid the direct approach, yet still get there quickly. You may want to come in from a rough terrain, sacrificing a couple of moves to hit from an unexpected side. All the parts of an AI have to work together, so may need to support suboptimal routes or pathfinding for alternative goals (get there without being seen, get there fastest, get there at same time as another group coming from another place, ...) AI are terrible in most strategy games (chess is an anomaly) because they can't coordinate pieces and usually take a brute force direct approach to everything.

It sounds like you have a solid plan and approach. The high level details can wait, but if you have a good idea of what you want now, you can design/plan for it now. If you can set up a way to find 'known paths that start near where i am now' then having too much data may not matter, you will be able to grab what you need efficiently.

[DarkLightHitomi]

The idea is that as the AI learns new routes, it can apply traits to the routes and use those traits to develop strategies. It can also assign weights to routes or routes sections, such as giving a section a weight indicating greater chance of enemy attack, better ambush site (both for making one and for defending against one), etc.

It finds routes, then compares along more aspects then just shortest.

I also realized, that defining obstacles as lines or polygons, lets me use collision detection techniques as well.

Now I just need a quick way to narrow which obstacles to check against etc.

Also note, that obstacles can have traits as well, such as "destroyable," "climbable," "can see/fire through," or "swimmable."