6 #include "monsterrace.h"
9 * Angband sorting algorithm -- quick sort in place
11 * Note that the details of the data we are sorting is hidden,
12 * and we rely on the "ang_sort_comp()" and "ang_sort_swap()"
13 * function hooks to interact with the data, which is given as
14 * two pointers, and which may have any user-defined form.
16 void ang_sort_aux(vptr u, vptr v, int p, int q,
17 bool(*ang_sort_comp)(vptr u, vptr v, int a, int b), void(*ang_sort_swap)(vptr u, vptr v, int a, int b))
35 while (!(*ang_sort_comp)(u, v, b, z)) b--;
38 while (!(*ang_sort_comp)(u, v, z, a)) a++;
44 (*ang_sort_swap)(u, v, a, b);
50 /* Recurse left side */
51 ang_sort_aux(u, v, p, b, ang_sort_comp, ang_sort_swap);
53 /* Recurse right side */
54 ang_sort_aux(u, v, b + 1, q, ang_sort_comp, ang_sort_swap);
59 * Angband sorting algorithm -- quick sort in place
61 * Note that the details of the data we are sorting is hidden,
62 * and we rely on the "ang_sort_comp()" and "ang_sort_swap()"
63 * function hooks to interact with the data, which is given as
64 * two pointers, and which may have any user-defined form.
66 void ang_sort(vptr u, vptr v, int n,
67 bool(*ang_sort_comp)(vptr u, vptr v, int a, int b) , void(*ang_sort_swap)(vptr u, vptr v, int a, int b))
70 ang_sort_aux(u, v, 0, n - 1, ang_sort_comp, ang_sort_swap);
75 * Sorting hook -- comp function -- by "distance to player"
77 * We use "u" and "v" to point to arrays of "x" and "y" positions,
78 * and sort the arrays by double-distance to the player.
80 bool ang_sort_comp_distance(vptr u, vptr v, int a, int b)
82 POSITION *x = (POSITION*)(u);
83 POSITION *y = (POSITION*)(v);
85 POSITION da, db, kx, ky;
87 /* Absolute distance components */
88 kx = x[a]; kx -= p_ptr->x; kx = ABS(kx);
89 ky = y[a]; ky -= p_ptr->y; ky = ABS(ky);
91 /* Approximate Double Distance to the first point */
92 da = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
94 /* Absolute distance components */
95 kx = x[b]; kx -= p_ptr->x; kx = ABS(kx);
96 ky = y[b]; ky -= p_ptr->y; ky = ABS(ky);
98 /* Approximate Double Distance to the first point */
99 db = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
101 /* Compare the distances */
107 * Sorting hook -- comp function -- by importance level of grids
109 * We use "u" and "v" to point to arrays of "x" and "y" positions,
110 * and sort the arrays by level of monster
112 bool ang_sort_comp_importance(vptr u, vptr v, int a, int b)
114 POSITION *x = (POSITION*)(u);
115 POSITION *y = (POSITION*)(v);
116 grid_type *ca_ptr = &p_ptr->current_floor_ptr->grid_array[y[a]][x[a]];
117 grid_type *cb_ptr = &p_ptr->current_floor_ptr->grid_array[y[b]][x[b]];
118 monster_type *ma_ptr = &p_ptr->current_floor_ptr->m_list[ca_ptr->m_idx];
119 monster_type *mb_ptr = &p_ptr->current_floor_ptr->m_list[cb_ptr->m_idx];
120 monster_race *ap_ra_ptr, *ap_rb_ptr;
122 /* The player grid */
123 if (y[a] == p_ptr->y && x[a] == p_ptr->x) return TRUE;
124 if (y[b] == p_ptr->y && x[b] == p_ptr->x) return FALSE;
126 /* Extract monster race */
127 if (ca_ptr->m_idx && ma_ptr->ml) ap_ra_ptr = &r_info[ma_ptr->ap_r_idx];
128 else ap_ra_ptr = NULL;
129 if (cb_ptr->m_idx && mb_ptr->ml) ap_rb_ptr = &r_info[mb_ptr->ap_r_idx];
130 else ap_rb_ptr = NULL;
132 if (ap_ra_ptr && !ap_rb_ptr) return TRUE;
133 if (!ap_ra_ptr && ap_rb_ptr) return FALSE;
135 /* Compare two monsters */
136 if (ap_ra_ptr && ap_rb_ptr)
138 /* Unique monsters first */
139 if ((ap_ra_ptr->flags1 & RF1_UNIQUE) && !(ap_rb_ptr->flags1 & RF1_UNIQUE)) return TRUE;
140 if (!(ap_ra_ptr->flags1 & RF1_UNIQUE) && (ap_rb_ptr->flags1 & RF1_UNIQUE)) return FALSE;
142 /* Shadowers first (あやしい影) */
143 if ((ma_ptr->mflag2 & MFLAG2_KAGE) && !(mb_ptr->mflag2 & MFLAG2_KAGE)) return TRUE;
144 if (!(ma_ptr->mflag2 & MFLAG2_KAGE) && (mb_ptr->mflag2 & MFLAG2_KAGE)) return FALSE;
146 /* Unknown monsters first */
147 if (!ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills) return TRUE;
148 if (ap_ra_ptr->r_tkills && !ap_rb_ptr->r_tkills) return FALSE;
150 /* Higher level monsters first (if known) */
151 if (ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills)
153 if (ap_ra_ptr->level > ap_rb_ptr->level) return TRUE;
154 if (ap_ra_ptr->level < ap_rb_ptr->level) return FALSE;
157 /* Sort by index if all conditions are same */
158 if (ma_ptr->ap_r_idx > mb_ptr->ap_r_idx) return TRUE;
159 if (ma_ptr->ap_r_idx < mb_ptr->ap_r_idx) return FALSE;
162 /* An object get higher priority */
163 if (p_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx && !p_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx) return TRUE;
164 if (!p_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx && p_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx) return FALSE;
166 /* Priority from the terrain */
167 if (f_info[ca_ptr->feat].priority > f_info[cb_ptr->feat].priority) return TRUE;
168 if (f_info[ca_ptr->feat].priority < f_info[cb_ptr->feat].priority) return FALSE;
170 /* If all conditions are same, compare distance */
171 return ang_sort_comp_distance(u, v, a, b);
176 * Sorting hook -- swap function -- by "distance to player"
178 * We use "u" and "v" to point to arrays of "x" and "y" positions,
179 * and sort the arrays by distance to the player.
181 void ang_sort_swap_distance(vptr u, vptr v, int a, int b)
183 POSITION *x = (POSITION*)(u);
184 POSITION *y = (POSITION*)(v);
202 * Sorting hook -- Comp function -- see below
204 * We use "u" to point to array of monster indexes,
205 * and "v" to select the type of sorting to perform on "u".
207 bool ang_sort_art_comp(vptr u, vptr v, int a, int b)
209 u16b *who = (u16b*)(u);
210 u16b *why = (u16b*)(v);
217 /* Sort by total kills */
220 /* Extract total kills */
221 z1 = a_info[w1].tval;
222 z2 = a_info[w2].tval;
224 /* Compare total kills */
225 if (z1 < z2) return TRUE;
226 if (z1 > z2) return FALSE;
230 /* Sort by monster level */
234 z1 = a_info[w1].sval;
235 z2 = a_info[w2].sval;
238 if (z1 < z2) return TRUE;
239 if (z1 > z2) return FALSE;
243 /* Sort by monster experience */
246 /* Extract experience */
247 z1 = a_info[w1].level;
248 z2 = a_info[w2].level;
250 /* Compare experience */
251 if (z1 < z2) return TRUE;
252 if (z1 > z2) return FALSE;
256 /* Compare indexes */
262 * Sorting hook -- Swap function -- see below
264 * We use "u" to point to array of monster indexes,
265 * and "v" to select the type of sorting to perform.
267 void ang_sort_art_swap(vptr u, vptr v, int a, int b)
269 u16b *who = (u16b*)(u);
281 bool ang_sort_comp_quest_num(vptr u, vptr v, int a, int b)
283 QUEST_IDX *q_num = (QUEST_IDX *)u;
284 quest_type *qa = &quest[q_num[a]];
285 quest_type *qb = &quest[q_num[b]];
290 return (qa->comptime != qb->comptime) ?
291 (qa->comptime < qb->comptime) :
292 (qa->level <= qb->level);
295 void ang_sort_swap_quest_num(vptr u, vptr v, int a, int b)
297 QUEST_IDX *q_num = (QUEST_IDX *)u;
310 * @brief ペット入りモンスターボールをソートするための比較関数
311 * @param u 所持品配列の参照ポインタ
315 * @return 1の方が大であればTRUE
317 bool ang_sort_comp_pet(vptr u, vptr v, int a, int b)
319 u16b *who = (u16b*)(u);
324 monster_type *m_ptr1 = &p_ptr->current_floor_ptr->m_list[w1];
325 monster_type *m_ptr2 = &p_ptr->current_floor_ptr->m_list[w2];
326 monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
327 monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
332 if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
333 if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
335 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return TRUE;
336 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return FALSE;
338 if (r_ptr1->level > r_ptr2->level) return TRUE;
339 if (r_ptr2->level > r_ptr1->level) return FALSE;
341 if (m_ptr1->hp > m_ptr2->hp) return TRUE;
342 if (m_ptr2->hp > m_ptr1->hp) return FALSE;
350 * @brief モンスター種族情報を特定の基準によりソートするための比較処理
351 * Sorting hook -- Comp function -- see below
352 * @param u モンスター種族情報の入れるポインタ
354 * @param a 比較するモンスター種族のID1
355 * @param b 比較するモンスター種族のID2
356 * @return 2の方が大きければTRUEを返す
357 * We use "u" to point to array of monster indexes,
358 * and "v" to select the type of sorting to perform on "u".
360 bool ang_sort_comp_hook(vptr u, vptr v, int a, int b)
362 u16b *who = (u16b*)(u);
363 u16b *why = (u16b*)(v);
370 /* Sort by player kills */
373 /* Extract player kills */
374 z1 = r_info[w1].r_pkills;
375 z2 = r_info[w2].r_pkills;
377 /* Compare player kills */
378 if (z1 < z2) return TRUE;
379 if (z1 > z2) return FALSE;
383 /* Sort by total kills */
386 /* Extract total kills */
387 z1 = r_info[w1].r_tkills;
388 z2 = r_info[w2].r_tkills;
390 /* Compare total kills */
391 if (z1 < z2) return TRUE;
392 if (z1 > z2) return FALSE;
396 /* Sort by monster level */
400 z1 = r_info[w1].level;
401 z2 = r_info[w2].level;
404 if (z1 < z2) return TRUE;
405 if (z1 > z2) return FALSE;
409 /* Sort by monster experience */
412 /* Extract experience */
413 z1 = r_info[w1].mexp;
414 z2 = r_info[w2].mexp;
416 /* Compare experience */
417 if (z1 < z2) return TRUE;
418 if (z1 > z2) return FALSE;
422 /* Compare indexes */
428 * @brief モンスター種族情報を特定の基準によりソートするためのスワップ処理
429 * Sorting hook -- Swap function -- see below
430 * @param u モンスター種族情報の入れるポインタ
432 * @param a スワップするモンスター種族のID1
433 * @param b スワップするモンスター種族のID2
436 * We use "u" to point to array of monster indexes,
437 * and "v" to select the type of sorting to perform.
439 void ang_sort_swap_hook(vptr u, vptr v, int a, int b)
441 u16b *who = (u16b*)(u);
454 * hook function to sort monsters by level
456 bool ang_sort_comp_monster_level(vptr u, vptr v, int a, int b)
458 u16b *who = (u16b*)(u);
463 monster_race *r_ptr1 = &r_info[w1];
464 monster_race *r_ptr2 = &r_info[w2];
469 if (r_ptr2->level > r_ptr1->level) return TRUE;
470 if (r_ptr1->level > r_ptr2->level) return FALSE;
472 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return TRUE;
473 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return FALSE;
479 * @brief ペットになっているモンスターをソートするための比較処理
480 * @param u モンスターの構造体配列
482 * @param a 比較対象のモンスターID1
483 * @param b 比較対象のモンスターID2
484 * @return 2番目が大ならばTRUEを返す
486 bool ang_sort_comp_pet_dismiss(vptr u, vptr v, int a, int b)
488 u16b *who = (u16b*)(u);
493 monster_type *m_ptr1 = &p_ptr->current_floor_ptr->m_list[w1];
494 monster_type *m_ptr2 = &p_ptr->current_floor_ptr->m_list[w2];
495 monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
496 monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
501 if (w1 == p_ptr->riding) return TRUE;
502 if (w2 == p_ptr->riding) return FALSE;
504 if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
505 if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
507 if (!m_ptr1->parent_m_idx && m_ptr2->parent_m_idx) return TRUE;
508 if (!m_ptr2->parent_m_idx && m_ptr1->parent_m_idx) return FALSE;
510 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return TRUE;
511 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return FALSE;
513 if (r_ptr1->level > r_ptr2->level) return TRUE;
514 if (r_ptr2->level > r_ptr1->level) return FALSE;
516 if (m_ptr1->hp > m_ptr2->hp) return TRUE;
517 if (m_ptr2->hp > m_ptr1->hp) return FALSE;
524 * @brief フロア保存時のgrid情報テンプレートをソートするための比較処理
525 * @param u gridテンプレートの参照ポインタ
527 * @param a スワップするモンスター種族のID1
528 * @param b スワップするモンスター種族のID2
529 * @return aの方が大きければtrue
531 bool ang_sort_comp_cave_temp(vptr u, vptr v, int a, int b)
533 grid_template_type *who = (grid_template_type *)(u);
535 u16b o1 = who[a].occurrence;
536 u16b o2 = who[b].occurrence;
546 * @brief フロア保存時のgrid情報テンプレートをソートするためのスワップ処理 / Sorting hook -- Swap function
547 * @param u gridテンプレートの参照ポインタ
549 * @param a スワップするモンスター種族のID1
550 * @param b スワップするモンスター種族のID2
553 void ang_sort_swap_cave_temp(vptr u, vptr v, int a, int b)
555 grid_template_type *who = (grid_template_type *)(u);
557 grid_template_type holder;
570 * @brief 進化ツリーをソートするためモンスター種族の判定関数 /
571 * Sorting hook -- Comp function
574 * @param a 比較したいモンスター種族ID1
575 * @param b 比較したいモンスター種族ID2
576 * @return 2が大きければTRUEを返す
578 bool ang_sort_comp_evol_tree(vptr u, vptr v, int a, int b)
580 int **evol_tree = (int **)u;
582 int w1 = evol_tree[a][0];
583 int w2 = evol_tree[b][0];
584 monster_race *r1_ptr = &r_info[w1];
585 monster_race *r2_ptr = &r_info[w2];
590 /* Used tree first */
591 if (w1 && !w2) return TRUE;
592 if (!w1 && w2) return FALSE;
594 /* Sort by monster level */
595 if (r1_ptr->level < r2_ptr->level) return TRUE;
596 if (r1_ptr->level > r2_ptr->level) return FALSE;
598 /* Sort by monster experience */
599 if (r1_ptr->mexp < r2_ptr->mexp) return TRUE;
600 if (r1_ptr->mexp > r2_ptr->mexp) return FALSE;
602 /* Compare indexes */
607 * @brief 進化ツリーをソートするため木構造のスワップ関数 /
608 * Sorting hook -- Swap function
611 * @param a スワップしたい木構造1
612 * @param b スワップしたい木構造2
613 * @return 2が大きければTRUEを返す
615 void ang_sort_swap_evol_tree(vptr u, vptr v, int a, int b)
617 int **evol_tree = (int **)u;
624 holder = evol_tree[a];
625 evol_tree[a] = evol_tree[b];
626 evol_tree[b] = holder;