• # NPC Conversation Techniques

Game Design and Theory

NPC Conversation Techniques

Courtesy of Amit Patel

Did I hear a request to discuss conversation engine techniques? That means an opportunity to repost for discussion my 26 screen paper on the best way to talk in a game. Booo-ha-ha-ha-ha-ha... : )

Seriously, I'm quite interested in how to work a solid, intuitive conversation, and any suggestions would be welcome.

# 1.0 Introduction

I've noticed a preponderance of posts all looking for various graphics tricks and techniques to use in their games. While I have no problem with this (in fact, I've learned quite a few things), there's been another programming problem on my mind lately. I haven't really though too heavily about it, but I'd like to throw a few ideas out in this forum and see where it goes. Results of open-discussion will be incorporated into this paper over time. Source code will inevitably follow, and the resulting monolith (as it seems to be taking on a life of its own) will be donated to the Rec.Games.Programmer Programming Encyclopedia if it is deemed useful enough.

## 1.0.1 Statement of Purpose

What I'm interested in creating is a conversation engine. I want to find a method of allowing communication between players and the computer characters (Non Player Characters or NPCs). Ideally it would allow the following:

1. Structured interaction between the player(s) and NPCs. This would allow conversations to take place, and would be the normal method of communication. It would allow player input, as well as the "standard greeting" given by an NPC from whom nothing else can be obtained. For example: it would allow players to negotiate with a shop owner, but also allow players to get information from a pedestrian ("Welcome to Port Nowhere". ).

2. Flexible dialogues based on external flags. This would allow NPCs to change conversations depending upon events in the storyline. For example: everyone in town will talk of nothing other than the slimy alien who ate the mayor. Once the alien is disposed of, they would be free to talk about other things.

3. It should be (fairly) easy for the players to determine how to ask certain questions, while not be merely a matter of walking through every branch of a conversation tree. For example: the venerable Sierra engine vs. Ultima Underworld (more detail on this later).

4. It should be fairly easy to program and maintain (including efficient storage) to allow many large conversations to be created, tested, and maintained without inordinate amounts of effort.

5. It should be flexible enough to provide better than 3rd grade levels of conversation, but extensible enough to handle modifications without undue difficulty.

6. It should be easy to use for novice players, but convenient for advanced players. This means it should also allow both keyboard and mouse input. If it can incorporate both seamlessly, then the player can decide what combination works best.

One other item to keep in mind, is that the conversation engine should be flexible enough to be incorporated into the rest of the interface. It must function smoothly with the movement engine, and any other control routines the program may require. What this list of requirements does, is prove that this problem will be more difficult to solve effectively than the graphics portion of my program, because the approach is not terribly well defined.

# 2.0 Common Approaches

There are three main approaches I have seen. They are:

1. Text Parsing
3. Hybrid Conversations

## 2.1 Text Parsing

Text Parsing Engine. A prompt is given to the player, nothing more. Input is typed in the following syntax: . This is a very old and refined method of input for a game, allowing all manner of action to be effected upon the environment. Generally, it has been used as the primary means of interacting with the game (as in the case of the old text adventure games), but has also been seen used as a primitive vehicle for interaction with NPCs. Examples of this sort of input would be: TADS (the Text ADventure game System), old Sierra games, Zork (really old people might remember this one : ) ), etc.

"Correct" actions are concealed from the player. Player needs to think about problems, rather than just walk though all the possibilities. Generally very good for puzzle creation, where the trick is to determine what to use X for to effect Y (for example: "put the key in the lock", "open the door").

The fact that it is the oldest form of input means that it has been resolved to a respectable level of complexity, and can simulate natural conversation fairly well. For example:

ASK THE MAN ABOUT THE WHALE

"Oh, the whale.  He's a real killer alright.  Nary a man sails
the sea without keeping one eye out for the whale."

"A boat?  Surely you're not thinking of sailing?  You're
crazier than I thought!"


"Correct" actions are often extremely difficult to determine, leading to frustration on the part of the user, especially if the puzzles are difficult, ill-conceived, or multi-part. This is especially difficult when a nice illustration or snazzy description does not match the name by which an object is referred to internally. Anyone who has ever played one of these games has seen the following:

TAKE THE WINE

"I don't know what a WINE is"

"I don't know what a FLASK is"

TAKE THE DAMN BOTTLE

"I don't know what a DAMN is"

TAKE THE BOTTLE

"You have taken the bottle."


This can quickly lead to frustration, as the player has difficulty in manipulating the interface. The largest problem is that user though patterns are always a mystery, as we have all seen (especially from beta testers: "What? You mean you tried to put the bathtub in your backpack and the game crashed? Gee... I never thought of that one...") Players, especially good ones, are notorious for trying the bizarre just to see what happens. (In fact, I 've always found that in these types of games, finding the little bizarre cases that they actually put into the game just to see if anyone tries it are the most interesting parts of these games.) Regardless, this form of communication is user un-friendly, despite the fact that it's relatively straightforward to program.

Menu Driven Conversations: These are conversations where the NPC says something and the player is presented with a multiple choice answer. Ultima Underworld II used this form of communication:

Angry Orc: "Hey! Nobody gets in here without the password."

A.  "Yes.  The password.  I know it."

B.  "The password?  Oh, I forgot it.  It's downstairs.  I'll be right back."



The choices are obvious, allowing the player to concentrate on their course of action, not "guess the right question". An interface should intrude upon the game as little as possible, allowing the player to invlove themselves with your game, not entangle themsleves in their hardware.

The conversation is a little more colorful (I've always loved choice "C".) and allows you to texture the conversation and use consistent slang to keep the player in character:

B. "Yea, the scourge of the east approaches."


The choices are a little too obvious. A player can merely save their game, and then try all the different branches of the conversation tree until they find the desired path. One possible solution is to allow save games only in certain locations, making it more trouble than it's worth to try all the options at will. On the other hand, this inconveniences the player and complicates the interface. (Personally. I don't mind the limited saves concept. It has the extra advantage of making combat a little more stressful than infinite save points does.)

Large numbers of choices are difficult to implement. If your game is a detective-type game, where you have large numbers of questions to ask large numbers of people, than the engine becomes unwieldy. It can also take a long time to traverse enough branches to get the desired result. This also detracts from the feel of the game.

## 2.3 Hybrid Engine

The hybrid engine is a combination of both previous systems. On the one hand, it presents the player with a list of actions that may be tried, allowing them to decide which is appropriate. It also obscures the painful obviousness of multiple-choice answers. From this basis, there are two major variations: the full-keyword version, and the basic choices plus optional keyword version. Both systems traverse conversations in the same way.

Typical conversation:

(Approach Fred, initiate conversation by selecting GREETING from list)

you: "Greetings friend."

response: "Greetings yourself, traveler.  Nice day today."

you: "I have traveled many lands and have acquired many
curiosities.  Perhaps you might have as well.
Would you care to barter a bit?"

response: "Ho there!  Is my profession so obvious that you can
spot me as a trader a mile off?  Of course!
Let us see what we have..."


### 2.3.1 The All-Keyword System

This engine presents the player with a list of keywords. The player picks a keyword, and the appropriate conversation proceeds from there. As the game progresses, more keywords are added to the list, allowing the player to revisit certain NPCs to see if they know anything new. An example of this type of game would be Bad Blood, a post-apocalyptic game. As you progressed in the game, new keywords would be added to your list of options. You would know which parts of conversations were important, and could then revisit key characters and try the new keywords.

The all-keyword system. This allows the player to talk to everyone about everything, and wait for the important keywords to show up. (Similar to the way you'd get points in the old Sierra games for doing correct things.) This could take some of the thought out of the game, as a player can simply run through conversations only looking for the 'beep' that indicates a new keyword. On the other hand, it allows some feedback to the player on their progress.

Another disadvantage, is that all intonation is predetermined. If you wish to ask a character about a certain item. Like a bottle, you choose bottle and the computer phrases your question for you. It takes away a player's ability to decide how they wish to phrase their question. Phrasing is especially useful when giving NPCs their own motivations. For example, you might want to lean on a weak-willed Orc to get information, but you would probably affect a more fawning tone in the presence of royalty, lest you find yourself shorter by a head. Intonation and interpretation is a vital part of communication (as seen by the net usage of : ) and similar icons to ensure that the intended meaning is not misinterpreted by the reader) and eliminating that aspect of conversation can detract from the player's association with their character.

### 2.3.2 The Standard Choices With Optional Keyword

This is similar to the first option, only this time, there are only basic choices presented to the player. There is also a blank space, where the player may try any other keywords they might like to try. This allows for some subtlety on the part of the designer. Key hints could be given and the keyword not added to the list (which would really annoy some players, who would accuse you of design flaws) or the list of choices could always be the same, relying on the character to keep track of what might be important. An example of this type of game would be The Summoning, a single-person dungeon game.

This system might seem to present some of the same limited choices that commonly have players trying vaguely related verbs. For example, the ubiquitous "use" verb that also stands for: twist, read, peel, pry, flick, turn on, etc. The other possible twist is that a player may find out a keyword before the plot would normally present it to them. This might be more common than initially thought, with stumped players frequently requesting this sort of information at the wrong time, or for someone who might by playing a second time. The solution would be to implement the EVENT flag concept, locking out certain keywords and conversations until certain events have happened. This system also suffers from the same lack of intonation as the previous flavor of this engine.

# 3.0 Conclusions

To be honest, I'm not quite sure. If I had to say that I was leaning towards any particular engine, I'd have to say it was type 2.3.2: standard action words with optional keyword. It seems to offer the strongest balance between player assistance and mystery. Unfortunately, it does nothing to solve the intonation issue. We would seem to need another option for our list of choices: one which allows some flair in conversation, allows the player to choose emotional context for their statements, yet obscure the choices somewhat, making the conversation less of a "try all the choices in order" process.

What I'd like to know is if anyone else has thought about this problem, if I've might have missed another way, or if there is a better way to implement one of these choices.

# 4.0 Coding Issues

As for the coding issues discussed initially, I 'd like to keep those in mind when discussing the possibilities (e.g. how could they be implemented) without clouding the issue with coding techniques just yet. (Because we all completely think through our ideas before we start programming them right? : ) ) Even so, we need to remember that the system should be extensible. If it works well, I intend to adapt the engine for use with examining objects and other sorts of interaction with the environment around the players. Flexibility is the key - we are looking to support both short conversations, as well as longer ones, and we will need to be able to maintain and dry-run our conversations to ensure that they flow. This section will be expanded along with the others as the topic matures.

# Bibliography

1. The Journal of Computer Game Design, Volume 6, Number 3. Estvanik, Steve. Designing a Mouse/Command Line Interface. February, 1993. p.10-11.
2. The Journal of Computer Game Design, Volume 6, Number 3. Em, Michele. How to write Interactive Characters and Dialogue. February, 1993. p. 14-5. (Before you ask: "The Journal of Computer Game Design is published six times a year. To subscribe to the Journal, send a check or money order for $36 ($50 outside North America) to:
The Journal of Computer Game Design
San Jose, CA 95132


Although I wouldn't if I were you. Not that the effort isn't appreciated, but it's hard to get in-depth articles from starving programmers who are already past deadlines. Articles are 1 - 2 pages and very abstract. The Journal has moved away from code-oriented articles in favor of "interactive storytelling" types. I also cannot vouch for the accuracy of this information. I stopped getting it a year ago after the first (and only year) of my subscription.)

3. Hartnell, Tim. Creating Adventure Games on Your Computer. Ballantine Books. New York, New York. 1984.

Report Article

## User Feedback

You need to be a member in order to leave a review

## Create an account

Register a new account

There are no reviews to display.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 0
• 0
• 0
• 4

• 11
• 15
• 21
• 26
• 11
• ### Similar Content

• By bzt
Hi,
I was looking for a way to effectively interpolate between skeletons represented by list of bones with position vector + orientation quaternion pairs. To my surprise, I couldn't find any good solution, not to my taste that is. I can't use NLERP because I need a general solution, and NLERP is only good for small distance interpolations. SLERP would be perfect, but I couldn't find a decent implementation, only slow ones, so I spent a lot of time looking at game engines and quaternion libraries and reading academic articles on the topic. Finally, I decided to collect my findings and write my own optimized version of SLERP, which focuses on performance over precision, and which I now would like to share with you.
Optimized cross-platform SLERP
I've started from the well known formula, as implemented by most C++ libraries, and used all the tricks I could find on the net. Then I took it to the next level, and made some more adjustments on my own speeding up a little bit more. Finally I ended up with two solutions:
1. one that is cross-platfrom, ANSI C solution that is easily embeddable in C++ and compatible with any C / C++ quaternion class (provided their data can be seen as 4 floats), very simple, very minimal. Use it freely if you want, MIT licensed
2. a SIMD version, which I had to leave half-ready, because my compiler and Intel disagree on what intrinsics should be provided for SSE, moreover the compiler does not work the way its documentation say it should :-( Shit happens. I would only recommend this for experimental purposes, also MIT licensed
Both versions are simpler and much faster than any implementations I could find, designed to be called in a loop several times. The only dependency they have is lib math (acosf, sinf). The SIMD version is half-ready, but even in this form it's almost 1.5 as fast as the other one, especially if you call it in a loop with memory prefetch on the quaternions.
If I made any mistake, miscalculated or mistyped something, let me know. If anybody has an idea how to overcome that intrinsics blockade I have, that would be appreciated very much, because I can clearly see the path how to make the code several times faster, only if I could get rid of the library calls. I also plan to create an ARM NEON port once I have that.
Cheers,
bzt
• By Ey-Lord
Hello everyone

I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy!

A bit of background:

I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when.

What brings me here today:

The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it.

Short description of the battle system:

No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible.

The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent.

What I want for my AI?

It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it.

In practice, it means a few requirements:

No dumb decision / do not fall into obvious player’s traps Exploit obvious flaws of the opponent Act in coordination when appropriate with other units Able to find who should be their focus in the player’s team (some notion of threat) Find the best move to use and if there is some kind of combo possible, use it

These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example).

What I have tried before?

I have tried or at least reviewed many different AI concepts so far.

-          A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all.

I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs.           (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me.        I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them)           I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way.
-        My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now.

What is my latest idea?

I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action:

A – Score every of its move (each move is a pair [skill, target]).

B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there).

So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills:

Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B.

Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well]

Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start]

Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3.

It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But…

The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move.

This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway.

So, my goal is to score properly buffs that:

Buffs the damage or healing output of someone           Buffs that buffs a skill that does the above

L    Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself)

-          I’m doing the above in 2 situations:

o   A : After a cast of the buff skill I’m evaluating

o   B : Without the cast of the buff, just like if it was that unit’s turn to play

-          Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B.

-          The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit.

-          Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff.

This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable)

What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway.

To come back with my initial goals:

No dumb decision / do not fall into obvious player’s traps
o   Not perfect but it should choose the best target whenever possible

Exploit obvious flaws of the opponent
o   Same as above

Act in coordination when appropriate with other units
o   This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average)

Able to find who should be their focus in the player’s team (some notion of threat)
o   It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard

Find the best move to use and if there is some kind of combo possible, use it
o   Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases.

I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you?

If you read that far…. thank you and I can"t wait to hear from you guys😊

• By Sword7
I googled for terrain collisions but found only some sources about flat worlds.   I want collision detection for spherical terrain worlds.   I have "3D Engine Design for Virtual Globe" book but it did not mention any algorithms about collision detection for landing, rolling, walking, crashing, etc...   Does anyone have any good sources for spherical terrain collision detection?
• By bzt
Hi guys,

I've an OpenGL question, which is quite math ad linear algebra related.
Let's assume we have two coordinate systems, S (scene) and O (object). I'd like to place O inside S, so I need O' (in S coordinates). Using the following transformation matrices I can do that: rotation, scale, displacement. So far so good. I have two questions though:

1) assuming the place of O' is specified with 4 points (zerus, and one for each axii unit vector end points) how can I calculate the required transformation matrices?
It's a "simple" case, as let's say points are P0, P1, P2, P3 and x = P0->P1, y = P0->P2, z = P0->P3. Also |x| = |y| = |z| (all has the same length) and they enclose 90 degree with each other. This surely can be solved using standard GL transformations easily, I just need an algorithm to calculate the matrices from P0, P1, P2, P3.

2) the more difficult question, how can I do the same if O' can be distorted, so |x| != |y| != |z| and their angle is not necessarily 90 degree? (Imagine that you "sit" on O, so O' became stretched and it's top became larger and moved to the side, so that angle(x, y) = 80 degree for example). How to get the required transformation matrices in this universal case, when you only know P0, P1, P2, P3?

Hope it's clear what I'm asking. I need an algorithm to generate a transformation matrix that I can then use to transform all points in O into O'.
bzt

• I'm working on a step-time strategy game (not sure if that's the proper term, but it moves in discrete time steps, about 4 frames, before pausing for input) with positively monstrous pathfinding calculations. I've solved the biggest of my problems already, but there is one algorithm that causes significant slowdown, and I'm sure it could be optimized, but I'm not sure how best to do that because my case has a unique property that isn't covered in any A* optimizations I've researched. (Or perhaps I'm just not thinking about it the right way.)
My game allows the creation of formations, which are defined as positional groupings of units relative to a leader. It's extremely important to the gameplay that these formations keep their shape as best as possible while balancing the need to move smoothly through any narrow spaces that constrict their shape. The algorithm I'm asking about now is responsible for choosing a path for the leader of the formation that (1) avoids unnecessarily traveling into narrow spaces and (2) always allows a certain amount of clearance between itself and obstacles, whenever those things are possible. Where I have found typical clearance-based approaches to A* fall short in addressing my problem is, ultimately, the leader will choose a path that goes through areas even just 1 space wide if there is no other option. In other words, I can't have the algorithm disregard those, but I can't have it explore those nodes either until it has explored the entirety of the rest of the map.
Here is my basic test map for this. The 5 green symbols at the top-left represent a formation led by the V in the center. The yellow circle at the center of the map is the goal.

Here is the solution that a regular A* would give, finding the shortest path:

Here is the solution I want (and the algorithm already does this, just slowly)

Here is the Python code that achieves this -- I know there are going to be some questions about what the vectors are and all of that, but basically, this is just a typical A* setup with the addition of a "c_cost," which is 0 if the given node has all the space that it wants (as defined by optimal_area), or 2 ^ the number of spaces missing from the amount of space we want.
def leader_pathfind(leader, going_to, treat_passable = [], treat_impassable = []): """ Seek the shorest path that attempts to avoid obstacles at a distance equal to that of the furthest member in the formation """ global game_width global game_height global diagonal_movement_cost global formation_dict at_now = leader['position'] treat_passable.append(going_to) # Prevents indefinite hanging while rerouting if an obstacle has moved to the destination if at_now == going_to: return [] formation_obj = formation_dict[leader['id']] vectors = formation_obj.get_formation_vectors() max_dimension = 0 for vector in vectors: for axis in vector: if abs(axis) > max_dimension: max_dimension = abs(axis) optimal_area = basic_pow(max_dimension * 2 + 1, 2) def clear_area(position): """ Check in square rings around the position for obstacles/edges of map, then return the total area that is passable within the square that first hits an obstacle/edge of map """ if not position_is_passable(position, treat_passable = treat_passable, treat_impassable = treat_impassable): return sys.maxint distance = 0 hit_obstacle = False while not hit_obstacle: distance += 1 corner_a = (position[0] - distance, position[1] - distance) corner_b = (position[0] + distance, position[1] + distance) outline = rectline(corner_a, corner_b) for point in outline: if not within_game_bounds(point): hit_obstacle = True break elif not position_is_passable(point, treat_passable = treat_passable, treat_impassable = treat_impassable): hit_obstacle = True break elif distance == max_dimension: # We have all the space we want, no need to compute further hit_obstacle = True break tent_area = rectfill(corner_a, corner_b) area = 0 for point in tent_area: if within_game_bounds(point): if position_is_passable(point, treat_passable = treat_passable, treat_impassable = treat_impassable): # Some stray diagonals may get counted here occasionally, but that should be acceptable for this purpose area += 1 return area def c(position): # c_cost is in terms of clear area relative to the optimal clearance area = clear_area(position) c_cost = 0 if area >= optimal_area else basic_pow(2, abs(area - optimal_area)) # Cost grows exponentially by powers of 2 for each point less than the optimal area return c_cost # Traditional A* # def h(position): return basic_distance(position, going_to) / 100.0 f_dict = {at_now: h(at_now)} g_dict = {at_now: 0} open_set = [at_now] closed_set = [] get_last = {} found_path = False current = at_now while len(open_set) > 0: current = open_set[0] for op in open_set: if op in f_dict.keys(): if f_dict[op] < f_dict[current]: current = op open_set.remove(current) closed_set.append(current) if current == going_to: found_path = True break for neighbor in neighbors(current, treat_passable = treat_passable, treat_impassable = treat_impassable): if neighbor in closed_set: continue if not neighbor in open_set: open_set.append(neighbor) movement_cost = diagonal_movement_cost if diagonally_adjacent(current, neighbor) else 1 tent_g = g_dict[current] + movement_cost tent_f = tent_g + c(neighbor) + h(neighbor) if not neighbor in f_dict.keys(): g_dict[neighbor] = tent_g f_dict[neighbor] = tent_f get_last[neighbor] = current else: if tent_f < f_dict[neighbor]: g_dict[neighbor] = tent_g f_dict[neighbor] = tent_f get_last[neighbor] = current if found_path: path = [going_to] current = going_to while current != at_now: current = get_last[current] path.append(current) path.reverse() path.pop(0) return path else: write_log('leader_pathfind: could not find a path from ' + str(at_now) + ' to ' + str(going_to)) return False Jump Point Search, which I've used elsewhere, relies on the assumption of a uniform-cost grid, so I believe I need to rely on abstracting my map down to a smaller number of abstract nodes, and I'm at a loss for how I would do that for this case. What I've read on using abstract nodes rely on things like identifying entrances/exits from abstract nodes, but that won't be useful if the algorithm chooses a node with acceptable entrance/exit points but lots of obstacles in the middle. Here is an arbitrarily chosen slice of the map with the correct path:

Broken up into abstract 5x5 nodes, I am failing to see a pattern I could rely on to give the algorithm the information it needs, especially since a crucial part of the path rests right on the right edge of the two leftmost abstract nodes. To know that this is the correct path, i.e. has sufficient clearance, it would need to calculate the clearance from that edge, dipping into the nodes in the middle. So I can't choose nodes that will be helpful without already having the information that I need the nodes to speed up the calculation of.
That's as far as I've gotten with my thought process. Can anyone make any suggestions, general or specific? Thanks in advance
×