Quote:Original post by makar
I would certainly suggest against cheating in order to save processor power. Worse-case scenario you can just do a random walk and this wouldn't take up any processing power. Cheating agents soon get found out, and this is just becomes frustrating to the users of the game. Think 'turing test'.

Every game AI cheats to some extent. Game AIs aren't expected to interpret a graphical display the way a human does. They also aren't usually expected to pass any turing tests. If it comes down to it, it's usually better to cheat than to cut a feature out of a game because it couldn't be solved without cheating. A lot of games even have the opposite of cheating, where the AI is intentionally made unaware of information that a human would have available, since the goal isn't always to make the AI behave like a human.

Quote:
Every game AI cheats to some extent. Game AIs aren't expected to interpret a graphical display the way a human does.

I'm afraid I disagree quite heavily with this. In fact, I am currently working on a game sequel where my aim is to re-write the AI system so that it no longer cheats because it could be very frustrating for the user.

Although it depends what sort of AI system you're creating though, because there are certainly times when you may want to cheat in order to add to the entertainment. But I think that if you're writing an AI system that is meant to represent a player of some sort, I would strived to ensure that the AI can only 'see' what the human would see and can only perform operations the human can perform. Playing against a cheating AI can be extremely frustrating, no-one likes competeting against a cheat. Of course the overall aim for an AI system is to perform entertainment for the user, but in many cases, I would argue that the AI system that cheats will not give good entertainment.

Quote:Original post by DaAnde
I feel that an AI should be the same as a regular player so in my picture above the AI needs to find some tinder in order to start a fire.

Well, based on your example image I am going to assume that you have a simple grid-based map with three possible cell types : tree, tinder, and open space.

Typically, in exploration type problems you first want to identify elements of the map that are relevant to your particular search goal, and make logical assumptions based on these elements as humans tend to do in real life.

If finding tinder is the goal, then logically we would look for tinder in the near vicinity of wooded areas as opposed to open-areas. Given the one example map you created, this is the only assumption that can be derived from the map that could aid in finding the timber more quickly.

To represent the assumption that tinder would more likely be near trees, you would weight the cells adjacent to tree cells in the grid with more favorable weightings, with these rewards diminishing the farther away from the tree you get. Your agent would then commence a walk through the grid, making greedy decisions and choosing successor cells with higher values where available. Doing this would make the agent prioritize searching wooded areas over searching open-space. Previously-visited cells would have their weights diminished to represent the fact that they have already been explored and are no longer of significant value to the search.

The proper term for these weighted grids would be "influence maps" I believe. There are plenty of papers available on the net discussing influence maps, so you should be able to devise a pretty workable solution to this problem using influence map techniques.

Quote:Original post by AngleWyrm
This looks like a Search problem. You have a clearly defined goal, but don't know where it is.

Which means it is not clearly defined... ;)

I read the first post and did a word find "dijkstra" and it did not appear!

Dijkstra's algorithm isn't the fastest search algorithm BUT it doesn't require a destination so it is used for resource gathering in strategy games.

Because the character in your diagram cant see the target, you will need to implement a simple line of sight algorithm that determines whether two tiles are visible from each other (no obstructions in a straight line).

Once the line of sight algorithm compares the characters position with every other tile on the map, there will be two hidden tiles in sight, one leading to a dead end, another that leads to the goal.

So the character will need to make a choice between the dead end route (just as one would in real life), the route could be chosen at random.

If the character chose to move to the hidden tile leading to the dead end, the line of sight algorithm would reveal no more hidden tiles to go to so he would then choose to take the shortest path to the last hidden spot that was found (the one leading to the goal). Note: because this time the destination is known, A faster search algorithm such as A* may be used.

Well my first attempt at posting an image failed...

Perhaps this will work.