Алгоритм дерева

Question

Я думал сегодня о идее небольшой игры и наткнулся на ее реализацию. Идея состоит в том, что игрок может совершить серию ходов, которые вызывают небольшой эффект, но если это сделано в определенной последовательности, это приведет к большему эффекту. Пока все хорошо, я знаю, как это сделать. Очевидно, мне пришлось усложнять задачу (потому что мы любим усложнять ее), поэтому я подумал, что может быть несколько возможных путей для последовательности, которые будут вызывать больший эффект, хотя и разные. Кроме того, частью некоторых последовательностей может быть начало других последовательностей, или даже целые последовательности могут содержаться другими более крупными последовательностями. Теперь я не знаю наверняка лучший способ реализовать это. У меня были некоторые идеи.

1) Я мог бы реализовать круговой n-связанный список. Но так как список шагов никогда не заканчивается, я боюсь, что это может вызвать переполнение стека ™. Идея состоит в том, что каждый узел будет иметь n детей и после получения команды он может привести вас к одному из его детей или, если ни один из детей не будет доступен для такой команды, приведет вас к началу. По прибытии на любых детей будет выполняться пара функций, вызывающих небольшой и большой эффект. Это может, однако, привести к большому количеству дублированных узлов на дереве, чтобы справиться со всеми возможными последовательностями, заканчивающимися на этом конкретном ходу с различными эффектами, что может быть болью для поддержания, но я не уверен. Я никогда не пробовал что-то такое сложное по коду, только теоретически. Существует ли этот алгоритм и есть имя? Это хорошая идея?

2) Я мог бы реализовать конечный автомат. Затем вместо того, чтобы блуждать по связанному списку, у меня будет гигантский вложенный коммутатор, который будет вызывать функции и соответственно обновлять состояние машины. Кажется, проще реализовать, но ... ну ... не кажется забавным ... и не ellegant. Гигантские переключатели всегда кажутся мне уродливыми, но будет ли это работать лучше?

3) Предложения? Я хорош, но я далеко неопытен. Хорошая вещь в области кодирования заключается в том, что независимо от того, насколько странно ваша проблема, кто-то решил ее в прошлом, но вы должны знать, где искать. У кого-то может быть лучшая идея, чем у меня, и я действительно хотел услышать предложения.

Answer 1

Я не совсем уверен, что я точно понимаю, что вы говорите, но, как аналог, скажите, что кто-то вводит бесконечный поток чисел на клавиатуре. «117» - это волшебная последовательность, «468» - другая, «411799» - другая (которая содержит первую).

Таким образом, если пользователь вводит:

вы хотите, чтобы огонь 'волшебные события' в * s:

55468 * 4117 * 99 *

или что-то в этом роде, не так ли? Если это, аналогичные проблемы вы говорите, то что о чем-то вроде (Java-подобный псевдокод):

MagicSequence fireworks = new MagicSequence(new FireworksAction(), 1, 1, 7); 
MagicSequence playMusic = new MagicSequence(new MusicAction(), 4, 6, 8); 
MagicSequence fixUserADrink = new MagicSequence(new ManhattanAction(), 4, 1, 1, 7, 9, 9); 

Collection<MagicSequence> sequences = ... all of the above ...; 

while (true) { 
    int num = readNumberFromUser(); 
    for (MagicSequence seq : sequences) { 
    seq.handleNumber(num); 
    } 
} 

в то время как MagicSequence есть что-то вроде:

Action action = ... populated from constructor ...; 
int[] sequence = ... populated from constructor ...; 
int position = 0; 

public void handleNumber(int num) { 
    if (num == sequence[position]) { 
    // They've entered the next number in the sequence 
    position++; 
    if (position == sequence.length) { 
     // They've got it all! 
     action.fire(); 
     position = 0; // Or disable this Sequence from accepting more numbers if it's a once-off 
    } 
    } else { 
    position = 0; // missed a number, start again! 
    } 
} 

Answer 2

То, что вы описываете, очень похоже на дерево технологий в живой цивилизации.

Я не знаю, как создатели Civ построили их, но я был бы склонен использовать мультиграфию для представления возможных «ходов» - там будут некоторые, с которыми вы можете начать без «опыта», и как только вы В них будет множество путей до конца.

Выделите, какие потенциальные варианты вы можете иметь на каждом этапе игры, а затем нарисуйте линии, идущие от некоторых вариантов к другим.

Это должно дать вам начало реализации, поскольку графики [относительно] легкие концепции для реализации и использования.

Answer 3

Возможно, вам захочется реализовать конечный автомат, но вам не нужно жестко переходить к состояниям.
Попробуйте сделать график состояний, где связь между состоянием A и состоянием B будет означать, что A может привести к B.
Затем вы можете пересечь график во время выполнения, чтобы найти, куда идет игрок.

Edit: Вы можете определить график узел как:
-state-ид
-list ссылок на другие государства, , где каждое звено определяет:
-state-идентификатор
-precondition, список состояний что необходимо посетить перед переходом в это состояние

Answer 4

Звучит как neural network.Вы можете создать его и обучить его распознаванию шаблонов, которые вызывают различные эффекты, которые вы ищете.

Answer 5

То, что вы описываете, звучит несколько похоже на граф зависимости или граф слов. Вы можете посмотреть на них.

Answer 6

создать небольшую государственную машину для каждый эффект, который вы хотите. при каждом действии пользователя, «транслировать» его на все государственные машины. большинство из них позаботится, но некоторые будут продвигаться или, может быть, вернуться назад. когда один из них достигает цели, производят желаемый эффект.

, чтобы сохранить код аккуратным, не жестко кодировать государственные машины, вместо этого построить простую структуру данных, которая кодирует граф состояний: каждое состояние представляет собой узел со списком интересных событий, каждый из которых указывает на узел следующего состояния , Состояние каждой машины - это просто ссылка на соответствующий узел состояния.

Редактировать: Кажется, совет Коуэна эквивалентен этому, но он оптимизирует свои государственные машины, чтобы выразить только простые последовательности. кажется достаточно для вашей конкретной проблемы, но более сложные условия могут потребовать более общего решения.

Answer 7

@Cowan, @Javier: Хорошая идея, если я добавлю к ней?

Пусть объекты MagicSequence прослушивают входящий поток пользовательского ввода, который уведомляет их о вводе (широковещании) и позволяет каждому из них добавить вход туда внутреннего входного потока. Этот поток очищается, когда вход не является ожидаемым следующим входом в шаблон, который заставил MagicSequence запустить его действие. Как только шаблон будет завершен, запустите действие и очистите внутренний входной поток.

Оптимизируйте это, подавая только входные данные MagicSequences, которые ждут его. Это можно сделать двумя способами:

1. У вас есть объект, который позволяет всем MagicSequences связываться с событиями, которые соответствуют номерам в их шаблонах. MagicSequence (1,1,7) добавит себя к got1 и got7, например:

   UserInput.got1 + = MagicSequnece [i].SendMeInput;

2. Вы можете оптимизировать это, чтобы после каждого входа MagicSequences отменял регистрацию из недействительных событий и регистрировал их с допустимыми.