000 06734nam a2201225Ia 4500
000 04563ntm a2200205 i 4500
001 76012
003 0
005 20250920173725.0
008 190130n 000 0 eng d
010 _z
_z
_o
_a
_b
015 _22
_a
016 _2
_2
_a
_z
020 _e
_e
_a
_b
_z
_c
_q
_x
022 _y
_y
_l
_a2
024 _2
_2
_d
_c
_a
_q
028 _a
_a
_b
029 _a
_a
_b
032 _a
_a
_b
035 _a
_a
_b
_z
_c
_q
037 _n
_n
_c
_a
_b
040 _e
_erda
_a
_d
_b
_c
041 _e
_e
_a
_b
_g
_h
_r
043 _a
_a
_b
045 _b
_b
_a
050 _a
_a
_d
_b2
_c0
051 _c
_c
_a
_b
055 _a
_a
_b
060 _a
_a
_b
070 _a
_a
_b
072 _2
_2
_d
_a
_x
082 _a
_a
_d
_b2
_c
084 _2
_2
_a
086 _2
_2
_a
090 _a
_a
_m
_b
_q
092 _f
_f
_a
_b
096 _a
_a
_b
097 _a
_a
_b
100 _e
_e
_aMiana, Erlyn Joy I. and Pabustan, Charina R.
_d
_b4
_u
_c0
_q16
110 _e
_e
_a
_d
_b
_n
_c
_k
111 _a
_a
_d
_b
_n
_c
130 _s
_s
_a
_p
_f
_l
_k
210 _a
_a
_b
222 _a
_a
_b
240 _s
_s
_a
_m
_g
_n
_f
_l
_o
_p
_k
245 0 _a
_aA further enhancement of jump point search algorithm applied in beaware: a 3D role playing game
_d
_b
_n
_cMiana, Erlyn Joy I. and Pabustan, Charina R.
_h6
_p
246 _a
_a
_b
_n
_i
_f6
_p
249 _i
_i
_a
250 _6
_6
_a
_b
260 _e
_e
_a
_b
_f
_c
_g
264 _3
_3
_a
_d
_b
_cMarch 2016.46
300 _e
_e
_c28 cm.
_a142 pp.
_b
310 _a
_a
_b
321 _a
_a
_b
336 _b
_atext
_2rdacontent
337 _3
_30
_b
_aunmediated
_2rdamedia
338 _3
_30
_b
_avolume
_2rdacarrier
340 _2
_20
_g
_n
344 _2
_2
_a0
_b
347 _2
_2
_a0
362 _a
_a
_b
385 _m
_m
_a2
410 _t
_t
_b
_a
_v
440 _p
_p
_a
_x
_v
490 _a
_a
_x
_v
500 _a
_aThesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2016.
_d
_b
_c56
504 _a
_a
_x
505 _a
_a
_b
_t
_g
_r
506 _a
_a5
510 _a
_a
_x
520 _b
_b
_c
_aABSTRACT: Jump Point Search is an optimization to the A* search algorithm pathfinding algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain node's neighbors, as long as certain conditions relating to the grid are satisfied. It preserves A*'s optimality, while potentially reducing its running time by an order of magnitude. The researchers seek thoroughly each and every process of the algorithm and how they work. First, the algorithm will identify successors by pruning all the neighbors of the current node. In pruning function, the algorithm will compute for the fcost (which is the current estimated shortest path) by adding the gcost (total distance it has taken to get from the starting position to the current location) and the hcost (estimated distance from the current position to the goal destination). Second, if all neighbors were already pruned, the algorithm will jump to a node that has the smallest fcost. Third, if there is any jump point successor, step in that direction. If the neighboring node is an obstacle, return null to the set of successors. If the neighboring node is closer to the goal, add that to the set of successors. If the direction is diagonal and it is not a straight jump point, add that to the set of successors. If the neighbour is not a jump point, recurse again and step in the diagonal direction. Then repeat the process. There are three problems that the researchers encounter during the study. First is that the Jump Point Search Algorithm manipulates and search nodes at a single time. Computing and analyzing each node is a waste of time. The algorithm spends a lot of time computing for the fcost of each node. Researchers aim to reduce the time that the algorithm spends on computing for the fcost of the nodes by making the computation per block node. The algorithm will already compute for the fcost of the block nodes if the nodes are in the same direction. In this way, we will reduce the time that the algorithm spends in computing the fcost. Second problem is that there are unnecessary jump points expanded such as intermediary jump points. Intermediary jump points are nodes that are not not a jump point but still, the algorithm considers it and compute for its fcost. The goal is to eliminate the computation for the fcost of that intermediary jump point but removing the process of it in the algorithm. Last is that the algorithm doesn't support hexagonal type of grids. Jump point search algorithm is only applicable in a square type of grid. The researchers found out that this algorithm could also be applicable to hexagonal type of grid. To make this possible, the researchers analyse the code of generating the square grid and transforms it to hexagonal grid by adding the third coordinate which points out to be the two sides of the square, so adding another coordinate would make it look like a hexagonal grid which happens to have three identical sides. As a result, the enhanced algorithm algorithm is much faster to compute for the fcost than the existing algorithm so the speed of finding path is faster. The second solution also affects the speed of the algorithm because there is no more computation for the intermediary nodes. And last but not the least, the algorithm can now be applied in a hexagonal type of grid which is more convenient in finding the shortest path. This study is recommended for those programmers who will try to make a pathfinding game. This newly improved algorithm will help a lot on games especially if it is a RPG game. Also, for the gamers who love playing RPG game because this algorithm will surely be the fastest when it comes in pathfinding.
_u
521 _a
_a
_b
533 _e
_e
_a
_d
_b
_n
_c
540 _c
_c
_a5
542 _g
_g
_f
546 _a
_a
_b
583 _5
_5
_k
_c
_a
_b
590 _a
_a
_b
600 _b
_b
_v
_t
_c2
_q
_a
_x0
_z
_d
_y
610 _b
_b
_v
_t2
_x
_a
_k0
_p
_z
_d6
_y
611 _a
_a
_d
_n2
_c0
_v
630 _x
_x
_a
_d
_p20
_v
648 _2
_2
_a
650 _x
_x
_a
_d
_b
_z
_y20
_v
651 _x
_x
_a
_y20
_v
_z
655 _0
_0
_a
_y2
_z
700 _i
_i
_t
_c
_b
_s1
_q
_f
_k40
_p
_d
_e
_a
_l
_n6
710 _b
_b
_t
_c
_e
_f
_k40
_p
_d5
_l
_n6
_a
711 _a
_a
_d
_b
_n
_t
_c
730 _s
_s
_a
_d
_n
_p
_f
_l
_k
740 _e
_e
_a
_d
_b
_n
_c6
753 _c
_c
_a
767 _t
_t
_w
770 _t
_t
_w
_x
773 _a
_a
_d
_g
_m
_t
_b
_v
_i
_p
775 _t
_t
_w
_x
776 _s
_s
_a
_d
_b
_z
_i
_t
_x
_h
_c
_w
780 _x
_x
_a
_g
_t
_w
785 _t
_t
_w
_a
_x
787 _x
_x
_d
_g
_i
_t
_w
800 _a
_a
_d
_l
_f
_t0
_q
_v
810 _a
_a
_b
_f
_t
_q
_v
830 _x
_x
_a
_p
_n
_l0
_v
942 _a
_alcc
_cBK
999 _c25427
_d25427