forked from angband/angband
/
randname.c
214 lines (177 loc) · 4.64 KB
/
randname.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
/*
* File: randname.c
* Purpose: Random name generation
*
* Copyright (c) 2007 Antony Sidwell, Sheldon Simms
*
* This work is free software; you can redistribute it and/or modify it
* under the terms of either:
*
* a) the GNU General Public License as published by the Free Software
* Foundation, version 2, or
*
* b) the "Angband licence":
* This software may be copied and distributed for educational, research,
* and not for profit purposes provided that this copyright and statement
* are included in all such copies. Other copyrights may also apply.
*/
#include "angband.h"
#include "randname.h"
/* Markers for the start and end of words. */
#define S_WORD 26
#define E_WORD S_WORD
#define TOTAL 27
typedef unsigned short name_probs[S_WORD+1][S_WORD+1][TOTAL+1];
/*
* This function builds probability tables from a list of purely alphabetical
* lower-case words, and puts them into the supplied name_probs object.
* The array of names should have a NULL entry at the end of the list.
* It relies on the ASCII character set (through use of A2I).
*/
static void build_prob(name_probs probs, const char **learn)
{
int c_prev, c_cur, c_next;
const char *ch;
int i;
/* Build raw frequencies */
for (i = 0; learn[i] != NULL; i++)
{
c_prev = c_cur = S_WORD;
ch = learn[i];
/* Iterate over the next word */
while (*ch != '\0')
{
c_next = A2I(tolower((unsigned char)*ch));
probs[c_prev][c_cur][c_next]++;
probs[c_prev][c_cur][TOTAL]++;
/* Step on */
c_prev = c_cur;
c_cur = c_next;
ch++;
}
probs[c_prev][c_cur][E_WORD]++;
probs[c_prev][c_cur][TOTAL]++;
}
}
/*
* Use W. Sheldon Simms' random name generator algorithm (Markov Chain stylee).
*
* Generate a random word using the probability tables we built earlier.
* Relies on the A2I and I2A macros (and so the ASCII character set) and
* is_a_vowel (so the basic 5 English vowels).
*/
size_t randname_make(randname_type name_type, size_t min, size_t max, char *word_buf, size_t buflen, const char ***sections)
{
size_t lnum = 0;
bool found_word = FALSE;
static name_probs lprobs;
static randname_type cached_type = RANDNAME_NUM_TYPES;
assert(name_type > 0 && name_type < RANDNAME_NUM_TYPES);
/* To allow for a terminating character */
assert(buflen > max);
/* We cache one set of probabilities, only regenerate when
the type changes. It's as good a way as any for now.
Frankly, we could probably regenerate every time. */
if (cached_type != name_type)
{
const char **wordlist = NULL;
wordlist = sections[name_type];
(void)WIPE(lprobs, name_probs);
build_prob(lprobs, wordlist);
cached_type = name_type;
}
/* Generate the actual word wanted. */
while (!found_word)
{
char *cp = word_buf;
int c_prev = S_WORD;
int c_cur = S_WORD;
int tries = 0;
bool contains_vowel = FALSE;
lnum = 0;
/* We start the word again if we run out of space or have
had to have 10 goes to find a word that satisfies the
minimal conditions. */
while (tries < 10 && lnum <= max && !found_word)
{
/* Pick the next letter based on a simple weighting
of which letters can follow the previous two */
int r;
int c_next = 0;
assert(c_prev >= 0 && c_prev <= S_WORD);
assert(c_cur >= 0 && c_cur <= S_WORD);
r = randint0(lprobs[c_prev][c_cur][TOTAL]);
while (r >= lprobs[c_prev][c_cur][c_next])
{
r -= lprobs[c_prev][c_cur][c_next];
c_next++;
}
assert(c_next <= E_WORD);
assert(c_next >= 0);
if (c_next == E_WORD)
{
/* If we've reached the end, we check if we've
met the simple conditions, otherwise have
another go at choosing a letter for this
position. */
if (lnum >= min && contains_vowel)
{
*cp = '\0';
found_word = TRUE;
}
else
{
tries++;
}
}
else
{
/* Add the letter to the word and move on. */
*cp = I2A(c_next);
if (is_a_vowel(*cp))
contains_vowel = TRUE;
cp++;
lnum++;
assert(c_next <= S_WORD);
assert(c_next >= 0);
c_prev = c_cur;
c_cur = c_next;
}
}
}
return lnum;
}
/*
* To run standalone tests, #define RANDNAME_TESTING and link with
* with just z-rand.c from Angband.
*/
#ifdef RANDNAME_TESTING
#include <stdio.h>
#include <time.h>
bool is_a_vowel(int ch)
{
switch (ch)
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return (TRUE);
}
return (FALSE);
}
int main(int argc, char *argv[])
{
int i;
char name[256];
Rand_value = time(NULL);
for (i = 0; i < 20; i++)
{
randname_make(RANDNAME_TOLKIEN, 5, 9, name, 256, name_sections);
my_strcap(name);
printf("%s\n", name);
}
return 0;
}
#endif