Comment by gavanwoolery | Hacker News Reader

Comment by gavanwoolery | Hacker News Reader

Parent Full thread

As someone who has worked intensively both in the fields of rendering and AI, I can say there are easy and hard problems in both. There is much in the way of AI that we already know, it's just that your average developer actually knows very little about AI (not trying to be insulting, it's just been true in my experience) -- and much more so your average company or publisher does not care to fund AI beyond enemies that can throw themselves into your gun barrel. Propositional logic, expert systems, backwards chaining, and neural networks are very powerful tools that we know a lot about, but most games rarely implement (perhaps trivially at most). We still tend to hand-design/script quests, when these fields of AI could provide very powerful emergent gameplay. What it mostly boils down to (for the sake of interesting gameplay) is proper knowledge-representation (i.e. abstraction) and reasoning (a prolog-like reasoning system would be a good start). And of course, path-finding/locomotion is pretty much a given. Interestingly, it is less about implementing these and more about designing a game that can use them properly - almost without doubt you need to create a game world that functions on its own, where every NPC has its own set of motivations, which is a very different task from creating a game that is limited to what the player does.

Other than that, there are still plenty of hard problems left in rendering, especially with regards to effective procedural generation (which arguably falls more under modeling). Our ray tracing is still far from "realistic" - take a more complex scene than a table with a wine glass, and we can still usually discern the difference, especially with complex materials and subsurface scattering (human skin STILL does not look quite right). As it is, we are only able to calculate light travel by points (we use the term ray tracing, but typically every ray does a number of steps, unless every model is mathematically calculated). Light travel should be determined by complex volumes -- which is pretty much impossible to simulate on today's hardware ( O(n^6) magnitude at least - growing by volume, travel distance, number of objects, volume bounces (dear god), and number of pixels calculated ).

I hope I didn't seem to be implying there weren't hard problems in both fields-- but I do think there's a bigger gap in the current state of the art than you claim.

The path to realism in graphics is pretty clear because the real-world behavior of light is well-understood. There may be equations yet to be perfected, and challenges in efficiently simulating that behavior, but the direction is never in question; you can always tell if you've made it look more realistic or less.

By contrast, AI in games has reached a local maxima; the combination of pathfinding, scripted cues, an elaborate finite state machine, and a few basic heuristics is capable of simulating human behavior well enough, and with few enough glitches, that it presents a realistic universe to the player so long as they don't exceed the scripted bounds. However, if they do exceed those bounds, the whole thing appears paper-thin. You can extend the bounds with additional effort in scripting, but not infinitely, and with diminishing returns-- and doing so gets you no closer to having real AI which would be able to make those same decisions on its own.

Striking out and attempting to make an intelligent NPC-directed world from scratch... I'm not saying it's impossible, but I haven't seen anything, from AAA titles to indie games to tech demos, to imply it's coming soon.

But maybe that's just because I haven't seen the Minecraft of AI-driven gameplay yet.

Good points :)

I am actually working on such an AI system, believe it or not (As I am sure quite a few others are)! I don't doubt my algorithms, because I have already prototyped them and they work (at least well enough to create some interesting, if flawed gameplay), but I do doubt that I will ever get a game out that uses them effectively (making even a simple game is incredibly hard, and I have a bad habit of creating overly-complex stuff).

Your traditional AAA game does, as you mention, basically use finite state machines to determine enemy behavior (and incredibly simple ones, at that).

Why is a FSM bad?

Because someone MUST explicitly declare every combination of situation, and the paths between them.

How does my system work? It uses a combination of AI techniques that have been around a long time (just never used effectively in games).

1) Rules and queries (like prolog), with backwards chaining and propositional logic (basically a big, graph-based system). How might this work? Let's pose a few fake rules and a query. A) apples are red B) oranges are orange. C) apples and oranges are fruit D) red fruit is good...QUERY: are apples good? Using backwards chaining, this can easily be deduced.

2) Motivators and deterrents. Every NPC has their own set of motivations, as well as "bad" things they try to avoid. They attempt to maximize their output towards attaining their goals, prioritized with various points (i.e. get food: 1 point, stay alive: 10,000 points, etc)....the best outcome can be found with any traditional AI system (like a minmax tree, A*, or whatever is appropriate for the given case). This is not just about food or living, but can be emotional concepts like "seek happiness" or concepts that involve the physical world "find shelter"...

3) Basic AI for sensory and locomotion purposes (line of site, perception, planning, gathering knowledge, etc.)

4) Abstraction of communication -- not at the syntactical level, and not at the grammar level, but in its crudest terms ("higher level language")...I call it caveman-speak but there has to be a better phrase...i.e. "Me Hungry" or "Why You Steal" -- using sentence fragments, you can construct a variety of phrases without giving the computer a hard time interpreting it. On the surface, you can throw in the syntactical sugar to make it sound less crude to the user, but on the backend writing a full-blown english parser is not a wise idea.

5) There is more, but I won't type it out here...

In the simplest terms, think of it like an empty stage in a play. There is no director (Finite State Machine) but there are characters and props, and the characters have backstories/motivations/genetic makeup/birthrights that determine what they will do and how they will react to changes in their environment. When you have rules, motivators, and a knowledge base, you can let the AI run wild -- and producing new rules grows with linear complexity, rather than exponential (as with a FSM).

Alternatively, if you even played the Sims, imagine something like that, but with more comprehensive AI (NPCs seek to maximize their comfort levels (id) while acting within their restraints (ego/super ego)).

You can track my progress (or lack thereof) at gavanw.com...unfortunately I work a fulltime job in addition, so development is occasionally slow.

Very interesting, with your work on voxels will modellers soon have to model the inside of objects - eg) Rather than modelling the human 'skin', model each part - clothes, body, tissue, bone?

Well, traditional polygon-based systems will be around a long time, but I do plan to keep everything volumetric in my engine. However, for the most part a lot of the volumes are procedurally generated (i.e. the wood pattern inside a trunk is a function of distance and angle from the trunk's center).

Sounds like the Minecraft of AI-driven gameplay... I would like to subscribe to your newsletter :)

Sign me up as well. I look forward to small-scale deployments of more 'genuine' AI in games.

That makes 2 subscribers ;)

Make that 3.

I've always wondered why game rules have to be so rigid (use a state machine) and always thought it was the technology but what you described makes sense and makes use of older technology but in new applications.

I just took one AI course while in college but got hooked ever since.

Question: Can you expand on the motivators and deterrents concept? Specifically, how do you relate something like "getting food" with the world objects? Assigning points to specific world objects(apple, cow, chicken...) seems to get us back to a state-machine like game. Humans have experience (memory and patterns) to guide them, what would the characters have?

Yes, to answer your question, there are many ways to go about implementing it, but here is how I do it:

In reality, you have one knowledge base, which is simply a set of facts/rules about the world. For example...

a) berries are fruit b) red fruit is good (+1 score) c) green fruit is bad (-1 score) d) enemies are dangerous e) eating while in danger is bad (-10 score) f) eating while full is bad (-2 points)

In a finite state machine, you would have to have several combinations of state (are berries present? are enemies present? are you full? etc). Say (for argument's sake) you have 5 possible states (binary). In a FSM, this would have 32 possible permutations of the states, which all must have corresponding actions associated with them. In a motivation based system, it simply evaluates each state individually, and adds up the points. It chooses to pursue the state that gives the most points. So, here, that would be eating red fruit while enemies are not present.

The way prolog-like systems work, the computer does not have to have ANY idea what food or hunger or anything like that is -- it can be completely oblivious to abstract concepts. All it is doing, in essence, is (searching for and) matching strings. Those strings are the identifiers used for classes (or instances) of game world objects, NPCs, etc. So if you gave an NPC a motivator (kill(enemy) = +10 points, Bob = enemy, get_caught_doing(kill) = -100 points), it will find the best way to kill Bob while avoiding negative consequences. This is (obviously) metacode, and the actual implementation would require better organization and more explicit syntax.

Make sense?

Yup, makes sense.

I have written exactly 15 lines of prolog but I'm somewhat aware of how they work. This is great stuff, but as you said the devil is in the details. Please consider writing up your experiences and sharing it on HN.

Definitely, will do :) It is also encouraging to see that people are interested in this.

With AI, there's also the problem of being more accurate than you want to be. A triple-A title like MW3 or Skyrim is essentially "a movie you walk through". NPCs have lines, they follow a script.

You could easily have NPCs that run a little life simulation, (like in the early versions of Oblivion) but then you have the problem of NPCs going off the script. If you accurately simulate mental states, and some villager rolls a 1 on the d2000 mental state die, then proceeds to kill all the plot-critical NPCs in their village? Now you've got a more realistic, yet completely broken, game.

If you were to accurately simulate mental states, there would need to be some kind of cause like the player murdering all the NPC's friends in front of them to end up on 1 rather than a randomly generated value

It seems to me, the problem with AI as applied to gaming, is that just having "good AI" doesn't mean having the smartest AI that can kick the player's butt, it means having AI that the player can observe and formulate strategies against. If it doesn't behave in a human way, and make it's decisions clear to the player then it's not fun.

In short, for gaming the measure of good AI is "fun", not "intelligence".

Also, better rendering is generally better (unless you want a cartoony cell renderer).

Better AI might not always be better. You don't want stupid AI bugs, but you don't necessarily want the AI to be smarter than the player. You may want an AI with a realistic character, but maybe not. Good AI makes some sense in a sandbox world, but it's not necessarily fun.

> your average company or publisher does not care to fund AI beyond enemies that can throw themselves into your gun barrel

Ironically the game where I've seen the most convincing AI currently is the Forza Motorsport series (increasing with each release). There is nothing short of impressive in seeing opponent drivers trying to pressure you to fault, intentionally breaking on you way after the apex just when you are about to floor it, showing excess of confidence throwing them out of the track, or reacting to pressure you put on them (you can literally see some panicking or getting aggressive in their driving), learning to clock faster times lap after lap and race after race, and even from your own lines. Sure they're nowhere near a real human, and with experience you can land better times than the AI and outsmart them, but there's plenty of physics and graphics going on already and there are trade-offs to be made.

In a video game anything the player doesn't see is a waste of time. In the case of games with large branching story lines it's a tradeoff between putting effort in to content which might be unseen and adding "depth." AI is the same. A genius AI that does all kinds of magic in the background is useless if the player never gets to see the magic.

Games don't want true AI solutions, they want to entertain the player. Put enough veneer on the world to make the player suspend disbelief and move on. Anything else is a waste of money for the most part.

Reply on news.ycombinator.com