Сегодня: Пятница, 29.03.2024, 01:42 (МСК)| Здравствуйте, Гость| Мой профиль | Регистрация | Вход | RSS

Военные технологии на пользовательском рынке

Спецэффекты в Cinema4D

Blu-ray приводы для ПК

Новинки в области цифровых камер

Программы — виртуальные гитаристы
Главная » РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР

Популярно об ИИ/Lua для игр и не только. Часть 7

14.03.2011

Вот так, некогда популярная серия «Lua для игр и не только» ненадолго воскрешается в силу ряда причин. Во-первых, буквально в новогодние праздники мы засели с некоторыми читателями и специалистами по ИИ за виртуальным круглым столом (пообщались в чате), где обсудили направления развития серии «Популярно об ИИ». Как многие знают, новый сезон я стартовал с темы вероятностной логики. После чего многие начали спорить, потому как просили написать большей частью о генетических алгоритмах, или хотя бы совместить две темы в одну. В принципе, сами они немного близки:). Затем обратились студенты-читатели рубрики программирования, задав множество интересных вопросов, среди которых очень многие опять же пересекаются с генетическими алгоритмами. Люди, обучающиеся Lua, сказали, что соответствующая серия была интересной, но не полной, поскольку в ней не рассмотрено много насущных вопросов, таких как работа с внешними файлами, строками, подключение и взаимодействие с внешними API. И окончательно ситуацию «добил» один веселый читатель, который попросил у меня алгоритм для создания (генерации) кроссвордов на базе имеющегося словаря. В общем, все темы, так или иначе, пересекаются. Поэтому приступим.


Формируем первое задание


Перед тем как приступить к написанию генератора кроссвордов, мы захватим менее сложный пример, а именно в этом материале начнем создавать алгоритм преобразования слова «МУХА» в слово «СЛОН». Это стандартная детская головоломка, в рамках которой предлагается составить список промежуточных слов, в каждом из которых в отличие от предыдущего меняется только одна буква. Таким образом, создается некая взаимосвязанная цепочка. В данном случае мы рассмотрим основные методы, покажем наиболее оптимальный, параллельно захватим те области языка Lua, о которых еще не писалось.


Предварительная подготовка


Работать мы будем в программе Scite (бесплатно скачивается с http://scite.ruteam.ru), в нем уже имеется встроенный интерпретатор языка Lua версии 5.1.  Дополнительно нам понадобится объемный словарь, включающий четырехбуквенные слова, который можно довольно быстро найти в интернете, пройдясь по сайтам кроссвордистов. Я нашел один такой вариант на ресурсе http://chyjik.narod.ru, там он получился на чуть меньше чем 4000 слов. Перенес я его в обычный текстовый файл (XML мы делать не будем). Итак, поехали.


Чтение из файла


Возможны два варианта работы с файлами. Первый — поиск мы можем осуществлять внутри них, то есть, не создавая дополнительных массивов (таблиц), второй — мы вгружаем файл в массив (таблицу), отсортировав все данные. У каждого случая есть свои плюсы и минусы, но в силу большей простоты и понятности реализации выберем второй вариант.  

В текстовом файле, так получилось при копировании (Ctrl+C/Ctrl+V), что все четырехбуквенные слова стоят вначале строк, а через несколько пробелов идут их описания. Описания, в общем-то, нам тоже понадобятся, поэтому стоит задача построчного чтения с последующим разбиением строк. То есть, структурно это подразумевает написание двух простых функций (если не объединять их в одну), одна из которых производит построчное чтение, вторая — разбивает данные и заносит в массив. 

Итак, даю следующий фрагмент кода:

--создаем пустую 
--таблицу

dtable = {}

--счетчик для нее
kdt=1

--функция заполнения 
--массива словаря
function split_dict(str)
dtable[kdt]={}
local cap = str:sub(1, 4)
table.insert(dtable[kdt],cap)
cap = str:sub(6, -1)
table.insert(dtable[kdt], cap)
kdt=kdt+1
end

--читаем текстовый файл
for line in io.lines("E:\\dictionary.txt") do 
split_dict(line)
end

Проверять все можно через команду print(), например, выведя весь словарь:

for i=1,kdt-1 do
print (dtable[i][1], dtable[i][2])
end

Результат получится таким:



Вывод будет производиться с некоторой задержкой, но при этом стоит отметить, что она связана только с выводом, сама операция преобразования файлов в массив занимает очень мало времени (что опять же можно проверить строкой print(os.clock())). 

Теперь небольшие пояснения к коду. Операция for line in io.lines(путь к файлу) do что-то там end является оптимальным вариантом автоматизации, в рамках которого открывается файл в режиме чтения, запускается цикл построчечного чтения, пока не встречается значение nil, после этого сам файл автоматически закрывается. 

Функция split_dict получает на входе строку из текстового файла, автоматически создавая «второе измерение» для массива/таблицы dtable (строка dtable[kdt]={}) , и заполняет две, если говорить образно, колонки, в одну вносит первые четыре символа строки выделенные функцией str:sub(1, 4), во вторую (поскольку там несколько пробелов) с 6 символа до конца, что делается за счет функции str:sub(6, -1). Следует отметить, что если в качестве последнего символа указывается «-1», это обозначает конец строки. 

Таким образом, мы быстро и оперативно заполнили наш массив. Движемся дальше.


Разбиение слов на буквы


Я рассматривал листинги некоторых программ (на Java, C++ и т.п.) и там нередко можно встретиться с тем, что сами слова не только разбиваются на символы, но и символы преобразуются в их кодовые значения ASCII. Целесообразность такового в плане Lua не совсем понятна, потому как слово «МУХА» всегда будет равно слову «МУХА», но не равно «МУЗА». Вопросы строчных/заглавных тоже можно решить быстрым конвертированием одних в другие и наоборот. То есть, единственное, что нам в данном случае нужно, — это просто разбиение слов на буквы.  

Делаем мы его с помощью той же функции sub, но при этом создав двумерный массив/таблицу под названием result, и сделав для него отдельный счетчик. Все будет выглядеть так:

--таблица, содержащая
--результаты разбиения
--по буквам
result = {}

--ее счетчик
kr=-1

--функция разбиения
function split_word(str)
local bv
result[kr]={}
for i=1,4 do
bv=str:sub(i,i)
table.insert(result[kr], bv)
end
kr=kr+1
end

Теперь поясним, на входе функция split_word() получает слово, после чего открывает второе «измерение» таблицы/массива результатов, и заносит в нее четыре новых элемента — буквы, из которых состоит входное слово. Коэффициент kr мы приняли равным единице не спроста, поскольку -1-м и 0-м элементами у нас будут исходное и заключительное слова головоломки. 

Мы можем их и сразу внести, дописав снизу строки:

split_word(«МУХА»)
split_word(«СЛОН»)

Этап завершен, двигаемся дальше.


Начало перебора


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

--задаем массив букв
--по алфавиту
alpha={"А","Б","В","Г","Д","Е","Ё","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У",
"Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"}

--массив уместных
--слов
slova = {}
--его счетчик
ksl=1

--функция сверки
--со словарем
function sootv_dict(str, str_ish)
for i=1,kdt-1 do
if dtable[i][1] == str and dtable[i][1]~=str_ish then
slova[ksl]= dtable[i][1]
ksl=ksl+1
print(dtable[i][1],dtable[i][2])
end
end
end

--функция добавления
--одного символа
function perebor()
for i=1,33 do
str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4]
str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i]
sootv_dict(str4,str_ish)
end
end

perebor()
print(ksl-1) 

Итак, в рамках функции perebor() мы, во-первых, сохраняем исходное слово, для того, чтобы потом его исключить из вариантов, во-вторых, перебираем все варианты с изменением одного символа (буквы), совмещая символы с помощью операции конкатенации «..», после чего вызываем функцию сравнения со словарем. В ее рамках пока находится print(), распечатывающая все найденные варианты, также они заносятся в массив/таблицу slova. 
Из слова МУХА у нас получилось 11:
  • АУХА — Рыба семейства окуневых.
  • МАХА — Один из видов полбы.
  • МУЗА — Стихотворение А. Ахматовой.
  • МУКА — 1) Пищевой продукт, полученный размолом зерна различных культур; основное сырье для хлебопекарного, макаронного и кондитерского производств. 2) Стихотворение русского поэта XIX века Кольцова.
  • НУХА — Название города Шеки в Азербайджане до 1968 года.
  • МУНА — Река в Якутии, левый приток Лены.
  • МОХА — Город в Йемене, порт на Красном море.
  • МУРА — Приток Ангары.
  • МУСА — Исламский пророк.
  • МУТА — Древнеримская нимфа, рассказавшая Юноне о любви Юпитера к Ютурне; за что Юпитер лишил ее дара речи.
  • МУХУ — Остров в Балтийском море.



Дальше предлагаю подумать самостоятельно до следующей части статей этой серии


Итак, мы сейчас создали весь необходимый базис для дальнейших действий. Предлагаю на данном этапе остановиться и подумать, каким образом мы будем искать ветку преобразования от «МУХА» к «СЛОН». Большинство начинающих студентов склонится к варианту полного перебора. Поэтому, предлагаю вам попробовать реализовать все самостоятельным образом, а в продолжении материала опишу некоторые варианты решений. Естественно, блок перебора, отображенный сегодня — это просто затравка. Полный листинг сегодняшней программы дан внизу статьи под подписью.

Кристофер

Перепечатка материалов или их фрагментов возможна только с согласия автора


Полный листинг предварительной программы

dtable = {}
kdt=1
result = {}
kr=-1
alpha={"А","Б","В","Г","Д","Е","Ё","Ж","З","И","Й","К","Л","М","Н","О","П","Р","С","Т","У",
"Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Ъ","Э","Ю","Я"}
slova = {}
ksl=1

function split_dict(str)
--создаем второе измерение
dtable[kdt]={}
--вносим добавления
local cap = str:sub(1, 4)
table.insert(dtable[kdt],cap)
cap = str:sub(6, -1)
table.insert(dtable[kdt], cap)
kdt=kdt+1
end

--читаем текстовый файл
for line in io.lines("E:\\dictionary.txt") do 
split_dict(line)
end

---------------------------------------------------------------

function split_word(str)
local bv
result[kr]={}
for i=1,4 do
bv=str:sub(i,i)
table.insert(result[kr], bv)
end
kr=kr+1
end


split_word("МУХА")
split_word("СЛОН")

--------------------------------------------------------------

function sootv_dict(str, str_ish)
for i=1,kdt-1 do
if dtable[i][1] == str and dtable[i][1]~=str_ish then
slova[ksl]= dtable[i][1]
ksl=ksl+1
print(dtable[i][1],dtable[i][2])
end
end
end

function perebor()
for i=1,33 do
str_ish=result[-1][1]..result[-1][2]..result[-1][3]..result[-1][4]
str4 = alpha[i]..result[-1][2]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..alpha[i]..result[-1][3]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..alpha[i]..result[-1][4]
sootv_dict(str4,str_ish)
str4 = result[-1][1]..result[-1][2]..result[-1][3]..alpha[i]
sootv_dict(str4,str_ish)
end
end

perebor()
print(ksl-1)



Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Ассоциация боевых роботов
Рекомендуем...
Новости

Разделы

Опросы

Какой язык программирования вы считаете наиболее актуальным сегодня?
Всего ответов: 329

Друзья

3D-кино






Найти на сайте:








Об авторе       Контакты      Вопрос-ответ        Хостинг от uCoz