A-star algorithm - Revision history

Im383 at 02:26, 16 December 2021

2021-12-16T02:26:26Z

← Older revision		Revision as of 22:26, 15 December 2021
Line 15:		Line 15:

	== Theory, Methodology, and Algorithmic Discussions ==		== Theory, Methodology, and Algorithmic Discussions ==
	From its start as a path finding algorithm for a robot, A* Algorithm has grown to be a staple in modern optimization of shortest path algorithms. A* was built originally as a greed algorithm finding an initial solution and improving upon it while remaining in the created bounded space. According to "Integer programming" by Laurence Wolsey "The idea of a greedy heuristic is to construct a solution from scratch (the empty set. choosing at each step the item bringing the "best" immediate reward" <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This holds true for the ship travel example of the “Research on Ship Meteorological Route Based on A-Star Algorithm” study where an empty set was initialized and a greedy algorithm was first found based on a shortest distance heuristic from the goal. The solution was then improved upon through recursion or a feasible solution is not found. The heuristic is the other part of A* algorithm derived from a greedy search with a proper heuristic properly defining the cost between the nodes. "Integer Programming" states this by stating "Greedy heuristic have to be adapted to the particular structure. For ]shortest-path problems] there are several possible greedy heuristics that choose edge one after another until a tour is obtained." <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This use of a heuristic can be seen in ~~A Comparative Study~~ of A~~-Star Algorithms for Search and Rescue~~ in ~~Perfect Maze~~ where a path is found through a heuristic determined by distance of node from the goal.		From its start as a path finding algorithm for a robot, A* Algorithm has grown to be a staple in modern optimization of shortest path algorithms. A* was built originally as a greed algorithm finding an initial solution and improving upon it while remaining in the created bounded space. According to "Integer programming" by Laurence Wolsey "The idea of a greedy heuristic is to construct a solution from scratch (the empty set. choosing at each step the item bringing the "best" immediate reward" <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This holds true for the ship travel example of the “Research on Ship Meteorological Route Based on A-Star Algorithm” study where an empty set was initialized and a greedy algorithm was first found based on a shortest distance heuristic from the goal. The solution was then improved upon through recursion or a feasible solution is not found. The heuristic is the other part of A* algorithm derived from a greedy search with a proper heuristic properly defining the cost between the nodes. "Integer Programming" states this by stating "Greedy heuristic have to be adapted to the particular structure. For [shortest-path problems] there are several possible greedy heuristics that choose edge one after another until a tour is obtained." <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This use of a heuristic can be seen in all other application of A* in shortest path problems where a path is found through a heuristic determined by distance of node from the goal.

Im383 at 02:21, 16 December 2021

2021-12-16T02:21:19Z

← Older revision		Revision as of 22:21, 15 December 2021
Line 15:		Line 15:

	== Theory, Methodology, and Algorithmic Discussions ==		== Theory, Methodology, and Algorithmic Discussions ==
	From its start as a path finding algorithm for a robot, A* Algorithm has grown to be a staple in modern optimization of shortest path algorithms. A* was built originally as a greed algorithm finding an initial solution and improving upon it while remaining in the created bounded space. According to Integer programming by Laurence Wolsey "The idea of a greedy heuristic is to construct a solution from scratch (the empty set. choosing at each step the item bringing the "best" immediate reward" <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This holds true for the ship travel example of the “Research on Ship Meteorological Route Based on A-Star Algorithm” study where an empty set was initialized and a greedy algorithm was first found based on a shortest distance heuristic from the goal. The solution was then improved upon through recursion or a feasible solution is not found. The heuristic is the other part of A* algorithm derived from a greedy search with a proper heuristic properly defining the cost between the nodes. ~~According to~~ Integer Programming "Greedy heuristic have to be adapted to the particular structure. For ]shortest-path problems] there are several possible greedy heuristics that choose edge one after another until a tour is obtained." <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This use of a heuristic can be seen in A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze where a path is found through a heuristic determined by distance of node from the goal.		From its start as a path finding algorithm for a robot, A* Algorithm has grown to be a staple in modern optimization of shortest path algorithms. A* was built originally as a greed algorithm finding an initial solution and improving upon it while remaining in the created bounded space. According to "Integer programming" by Laurence Wolsey "The idea of a greedy heuristic is to construct a solution from scratch (the empty set. choosing at each step the item bringing the "best" immediate reward" <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This holds true for the ship travel example of the “Research on Ship Meteorological Route Based on A-Star Algorithm” study where an empty set was initialized and a greedy algorithm was first found based on a shortest distance heuristic from the goal. The solution was then improved upon through recursion or a feasible solution is not found. The heuristic is the other part of A* algorithm derived from a greedy search with a proper heuristic properly defining the cost between the nodes. "Integer Programming" states this by stating "Greedy heuristic have to be adapted to the particular structure. For ]shortest-path problems] there are several possible greedy heuristics that choose edge one after another until a tour is obtained." <ref name="Linear-Programming"> L.A. Wolsey, Integer Programming. Wiley, 1998. </ref>. This use of a heuristic can be seen in A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze where a path is found through a heuristic determined by distance of node from the goal.


Line 36:		Line 36:


	An early study of the algorithm was done in Beijing University of Technology in 2011 where the algorithm was used to track the fastest path through a maze. Three A* Algorithms were used with different heuristics based on Euclidian distance, Euclidian distance from start and from base of current path and angle from current position to the goal shown in variations of the standard A* Algorithm:		An early study of the algorithm was done in “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze” by Xiang Liu and Daoxiong Gong of Beijing University of Technology in 2011 where the algorithm was used to track the fastest path through a maze. Three A* Algorithms were used with different heuristics based on Euclidian distance, Euclidian distance from start and from base of current path and angle from current position to the goal shown in variations of the standard A* Algorithm:

	<math>f(n) = g(n) + h(n) </math>		<math>f(n) = g(n) + h(n) </math>
Line 46:		Line 46:
	Variation 3: <math> h(n) = w1l/L + w2\theta/\alpha </math> where <math> w </math> is a weight, <math> l/L </math> is the Euclidian distance, <math> \theta </math> is the angle from the starting point to the current position and <math> \alpha </math> is the angle from the ending point to the current position <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>		Variation 3: <math> h(n) = w1l/L + w2\theta/\alpha </math> where <math> w </math> is a weight, <math> l/L </math> is the Euclidian distance, <math> \theta </math> is the angle from the starting point to the current position and <math> \alpha </math> is the angle from the ending point to the current position <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>

	On all occasions at least one of the A* Algorithms out performed a depth search with the second heuristic performing the best "generally, in unknown maze, while only proximate location of target point is known, A∗ algorithm is better than depth-first search algorithm in searching, however when the heuristic functions are different, searching results are also different." <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>		On all occasions at least one of the A* Algorithms out performed a depth search with the second heuristic performing the best "generally, in unknown maze, while only proximate location of target point is known, A∗ algorithm is better than depth-first search algorithm in searching, however when the heuristic functions are different, searching results are also different." <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref> Figure 1 shows the results of the maze experiment using 10 perfect randomly generated mazes.

			[[File:Results of the perfect maze problem.png\|thumb\|center\|thumb\|691x691px\|Figure 1. Table showing the result for the ten perfect mazes test in “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze”<ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref> ]]


	Many discussions exist revolving the best use of the A* Algorithm and also where it is most highly utilized. One of them being the game industry, mainly used to find the shortest path. There is a plethora of shortest path algorithms but A* is one of the preferred methods.~~[4]~~ A* Algorithm is an implementation of heuristic search, a process that will give an estimation value from current node to goal node. This implementation will always find the smallest value optimal path using:
			Many discussions exist revolving the best use of the A* Algorithm and also where it is most highly utilized. One of them being the game industry, mainly used to find the shortest path. There is a plethora of shortest path algorithms but A* is one of the preferred methods.<ref name="hexagon">P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.</ref> A* Algorithm is an implementation of heuristic search, a process that will give an estimation value from current node to goal node. This implementation will always find the smallest value optimal path using:

	<math>f(n) = g(n) + h(n)</math>		<math>f(n) = g(n) + h(n)</math>
Line 56:		Line 58:
	where <math>n</math> is a node, <math>g(n)</math> is the distance from starting node to <math>n</math> node, and		where <math>n</math> is a node, <math>g(n)</math> is the distance from starting node to <math>n</math> node, and

	<math>h(n)</math> is a heuristic value of estimation distance from node n to finish node.<ref>P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.</ref>		<math>h(n)</math> is a heuristic value of estimation distance from node n to finish node.<ref name="hexagon">P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.</ref>

	One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.		One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.
Line 62:		Line 64:
	==Numerical Example==		==Numerical Example==

	The A* Algorithm is a great approach for finding the lowest-cost path between two points. In the Figure 1, we are seeking to find the shortest distance between two nodes.		The A* Algorithm is a great approach for finding the lowest-cost path between two points. In the Figure 2, we are seeking to find the shortest distance between two nodes.

	[[File:Figure Representative of Mapped Locations.png\|center\|thumb\|691x691px\|Figure 1. Representation of Mapped Locations]]		[[File:Figure Representative of Mapped Locations.png\|center\|thumb\|691x691px\|Figure 2. Representation of Mapped Locations]]


Line 89:		Line 91:


	Step 3: Since <math>f(C)</math> yields the smaller value, this value is chosen as taking the path between Node A and Node C. This path is highlighted yellow in Figure 2.		Step 3: Since <math>f(C)</math> yields the smaller value, this value is chosen as taking the path between Node A and Node C. This path is highlighted yellow in Figure 3.
	[[File:Map Highlighting Chosen Path from Node A to Node C.jpg\|alt=\|center\|thumb\|691x691px\|Figure 2. Map Highlighting the Chosen Path from Node A to Node C]]		[[File:Map Highlighting Chosen Path from Node A to Node C.jpg\|alt=\|center\|thumb\|691x691px\|Figure 3. Map Highlighting the Chosen Path from Node A to Node C]]


Line 107:		Line 109:


	Step 6: Since <math>f(H)</math> yields a smaller value, this value is chosen as taking the path between Nodes C to H. The path is highlighted yellow in Figure 3.		Step 6: Since <math>f(H)</math> yields a smaller value, this value is chosen as taking the path between Nodes C to H. The path is highlighted yellow in Figure 4.

	[[File:Map Highlighting Chosen Path from Node A through Node H.jpg\|center\|thumb\|691x691px\|Figure 3. Map Highlighting the Chosen Path from Node A through Node H]]		[[File:Map Highlighting Chosen Path from Node A through Node H.jpg\|center\|thumb\|691x691px\|Figure 4. Map Highlighting the Chosen Path from Node A through Node H]]


Line 126:		Line 128:


	Step 9: Since <math>f(I)</math> yields a smaller value, this value is chosen as taking the path from Nodes H to I. The path continues to be highlighted yellow in Figure 4.		Step 9: Since <math>f(I)</math> yields a smaller value, this value is chosen as taking the path from Nodes H to I. The path continues to be highlighted yellow in Figure 5.

	[[File:Map Highlighting Chosen Path from Node A through Node I.jpg\|center\|thumb\|690x690px\|Figure 4. Map Highlighting the Chosen Path from Node A through Node I]]		[[File:Map Highlighting Chosen Path from Node A through Node I.jpg\|center\|thumb\|690x690px\|Figure 5. Map Highlighting the Chosen Path from Node A through Node I]]


Line 145:		Line 147:


	Since <math>f(K)</math> is the smaller value, and K is the objective Node, the A* Algorithm has found the shortest path between Nodes A and K. The path is highlighted in Figure 5.		Since <math>f(K)</math> is the smaller value, and K is the objective Node, the A* Algorithm has found the shortest path between Nodes A and K. The path is highlighted in Figure 6.

	[[File:Map Highlighting Shortest Path from Node A through Node K.jpg\|center\|thumb\|690x690px\|Figure 5. Map Highlighting Shortest Path from Node A through Node K]]		[[File:Map Highlighting Shortest Path from Node A through Node K.jpg\|center\|thumb\|690x690px\|Figure 6. Map Highlighting Shortest Path from Node A through Node K]]

	==Application==		==Application==
Line 158:		Line 160:
	An analysis was conducted on the transportation system in Yangon, Myanmar<ref>Zar, Myat Thu and Sein, Myint Myint. “Using A* Algorithm For Public Transportation System in Yangon Area.” 2015 International Journal of Advanced Computational Engineering and Networking, vol. 3, issue 3, pp. 7 –10 </ref>. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.		An analysis was conducted on the transportation system in Yangon, Myanmar<ref>Zar, Myat Thu and Sein, Myint Myint. “Using A* Algorithm For Public Transportation System in Yangon Area.” 2015 International Journal of Advanced Computational Engineering and Networking, vol. 3, issue 3, pp. 7 –10 </ref>. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.

	[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Figure 6. Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]		[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Figure 7. Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]

Im383 at 00:48, 16 December 2021

2021-12-16T00:48:46Z

← Older revision		Revision as of 20:48, 15 December 2021
Line 37:		Line 37:

	An early study of the algorithm was done in Beijing University of Technology in 2011 where the algorithm was used to track the fastest path through a maze. Three A* Algorithms were used with different heuristics based on Euclidian distance, Euclidian distance from start and from base of current path and angle from current position to the goal shown in variations of the standard A* Algorithm:		An early study of the algorithm was done in Beijing University of Technology in 2011 where the algorithm was used to track the fastest path through a maze. Three A* Algorithms were used with different heuristics based on Euclidian distance, Euclidian distance from start and from base of current path and angle from current position to the goal shown in variations of the standard A* Algorithm:



	<math>f(n) = g(n) + h(n) </math>		<math>f(n) = g(n) + h(n) </math>
Line 47:		Line 45:

	Variation 3: <math> h(n) = w1l/L + w2\theta/\alpha </math> where <math> w </math> is a weight, <math> l/L </math> is the Euclidian distance, <math> \theta </math> is the angle from the starting point to the current position and <math> \alpha </math> is the angle from the ending point to the current position <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>		Variation 3: <math> h(n) = w1l/L + w2\theta/\alpha </math> where <math> w </math> is a weight, <math> l/L </math> is the Euclidian distance, <math> \theta </math> is the angle from the starting point to the current position and <math> \alpha </math> is the angle from the ending point to the current position <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>



	On all occasions at least one of the A* Algorithms out performed a depth search with the second heuristic performing the best "generally, in unknown maze, while only proximate location of target point is known, A∗ algorithm is better than depth-first search algorithm in searching, however when the heuristic functions are different, searching results are also different." <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>		On all occasions at least one of the A* Algorithms out performed a depth search with the second heuristic performing the best "generally, in unknown maze, while only proximate location of target point is known, A∗ algorithm is better than depth-first search algorithm in searching, however when the heuristic functions are different, searching results are also different." <ref name="early">Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.</ref>
Line 55:		Line 51:

	Many discussions exist revolving the best use of the A* Algorithm and also where it is most highly utilized. One of them being the game industry, mainly used to find the shortest path. There is a plethora of shortest path algorithms but A* is one of the preferred methods.[4] A* Algorithm is an implementation of heuristic search, a process that will give an estimation value from current node to goal node. This implementation will always find the smallest value optimal path using:		Many discussions exist revolving the best use of the A* Algorithm and also where it is most highly utilized. One of them being the game industry, mainly used to find the shortest path. There is a plethora of shortest path algorithms but A* is one of the preferred methods.[4] A* Algorithm is an implementation of heuristic search, a process that will give an estimation value from current node to goal node. This implementation will always find the smallest value optimal path using:



	<math>f(n) = g(n) + h(n)</math>		<math>f(n) = g(n) + h(n)</math>
Line 63:		Line 57:

	<math>h(n)</math> is a heuristic value of estimation distance from node n to finish node.<ref>P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.</ref>		<math>h(n)</math> is a heuristic value of estimation distance from node n to finish node.<ref>P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.</ref>



	One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.		One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.

Im383 at 00:46, 16 December 2021

2021-12-16T00:46:59Z

← Older revision		Revision as of 20:46, 15 December 2021
Line 18:		Line 18:


	~~Pseudo code exmaple of A* algorithm built of greedy algorithm: <br />~~
	~~open_list, closed_list = empty list of possible positions <br />~~
	~~adjacent_value=0 <br />~~
	~~next_position=null <br />~~
	~~push start_position to open_list <br />~~
	~~while open_list is not empty~~
	~~: current node = pop open_list~~
	~~: for each adjacent position of current_node (ap_current) with value (av_current)~~
	~~:: if adjacent_value is less than av_current or ap_current is in closed_list~~
	~~::: adjacent_value= av_current~~
	~~::: next_position= ap_current~~
	~~:: push ap_current to closed_list~~
	~~: push next_position to open_list~~

			Pseudo code example of A* algorithm built of greedy algorithm:

			<code>open_list, closed_list = empty list of possible positions
			adjacent_value=0
			next_position=null
			push start_position to open_list
			while open_list is not empty
			current node = pop open_list
			for each adjacent position of current_node (ap_current) with value (av_current)
			if adjacent_value is less than av_current or ap_current is in closed_list
			adjacent_value= av_current
			next_position= ap_current
			push ap_current to closed_list
			push next_position to open_list</code>


Line 68:		Line 68:
	One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.		One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non-playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.

	== Numerical Example ==		==Numerical Example==

	The A* Algorithm is a great approach for finding the lowest-cost path between two points. In the Figure 1, we are seeking to find the shortest distance between two nodes.		The A* Algorithm is a great approach for finding the lowest-cost path between two points. In the Figure 1, we are seeking to find the shortest distance between two nodes.
Line 157:		Line 157:
	[[File:Map Highlighting Shortest Path from Node A through Node K.jpg\|center\|thumb\|690x690px\|Figure 5. Map Highlighting Shortest Path from Node A through Node K]]		[[File:Map Highlighting Shortest Path from Node A through Node K.jpg\|center\|thumb\|690x690px\|Figure 5. Map Highlighting Shortest Path from Node A through Node K]]

	== Application ==		==Application==

	'''Public Transportation in Cities'''		'''Public Transportation in Cities'''
Line 177:		Line 177:


	== Conclusion ==		==Conclusion==

	Through the use of a serpentine node map system, using each road and intersection as an edge and node respectively and scoring each based on our characteristics, a basis was built on which to run the A* algorithm. The algorithm was then able to traverse the map finding the shortest, fastest, and most fuel-efficient path in order to minimize the inconvenience to the traveler and the environmental impact. Through the A* algorithm on the node map travel can be optimized to be more efficient and faster for both commercial and pedestrian travel.		Through the use of a serpentine node map system, using each road and intersection as an edge and node respectively and scoring each based on our characteristics, a basis was built on which to run the A* algorithm. The algorithm was then able to traverse the map finding the shortest, fastest, and most fuel-efficient path in order to minimize the inconvenience to the traveler and the environmental impact. Through the A* algorithm on the node map travel can be optimized to be more efficient and faster for both commercial and pedestrian travel.

	== References ==		==References==
	<references/>		<references />

Im383 at 00:21, 16 December 2021

2021-12-16T00:21:03Z

← Older revision		Revision as of 20:21, 15 December 2021
Line 18:		Line 18:


			Pseudo code exmaple of A* algorithm built of greedy algorithm: <br />
	open_list = empty list of possible positions <br />		open_list, closed_list = empty list of possible positions <br />
	~~closed_list~~ = ~~empty list of possible positions~~ <br />		adjacent_value=0 <br />
			next_position=null <br />
	push start_position to open_list <br />		push start_position to open_list <br />
	while open_list is not empty		while open_list is not empty
	: for each adjacent position		: current node = pop open_list
	:: ~~current~~		: for each adjacent position of current_node (ap_current) with value (av_current)
			:: if adjacent_value is less than av_current or ap_current is in closed_list
			::: adjacent_value= av_current
			::: next_position= ap_current
			:: push ap_current to closed_list
			: push next_position to open_list

Gs726 at 23:12, 15 December 2021

2021-12-15T23:12:29Z

← Older revision		Revision as of 19:12, 15 December 2021
Line 164:		Line 164:

	The approach to analysis with the implementation of the A* algorithm was similar to our initial approach. This proposed system in the Yangon area focused solely on the distance between nodes. To improve efficiency, an algorithm that includes data and analysis on traffic patterns, road closures and wait times for bus stops would aid users in optimizing their transportation selection. The use of the A* algorithm bus network in a region so heavily reliant on public transportation is a respectable strategy to address transportation concerns in the Yangon area.		The approach to analysis with the implementation of the A* algorithm was similar to our initial approach. This proposed system in the Yangon area focused solely on the distance between nodes. To improve efficiency, an algorithm that includes data and analysis on traffic patterns, road closures and wait times for bus stops would aid users in optimizing their transportation selection. The use of the A* algorithm bus network in a region so heavily reliant on public transportation is a respectable strategy to address transportation concerns in the Yangon area.


	'''Pathfinding in Video Games'''		'''Pathfinding in Video Games'''

Gs726 at 23:10, 15 December 2021

2021-12-15T23:10:10Z

← Older revision		Revision as of 19:10, 15 December 2021
Line 158:		Line 158:


	An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.		An analysis was conducted on the transportation system in Yangon, Myanmar<ref>Zar, Myat Thu and Sein, Myint Myint. “Using A* Algorithm For Public Transportation System in Yangon Area.” 2015 International Journal of Advanced Computational Engineering and Networking, vol. 3, issue 3, pp. 7 –10 </ref>. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.

	[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Figure 6. Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]		[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Figure 6. Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]

Gs726: Added Figure reference

2021-12-15T23:02:34Z

Added Figure reference

← Older revision		Revision as of 19:02, 15 December 2021
Line 160:		Line 160:
	An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.		An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.

	[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]		[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Figure 6. Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]

Gs726: centered image yangon sample data to fix formatting

2021-12-15T22:46:04Z

centered image yangon sample data to fix formatting

← Older revision		Revision as of 18:46, 15 December 2021
Line 160:		Line 160:
	An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.		An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.

	[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png~~\|left~~\|thumb\|578x578px\|Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)]]		[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|thumb\|578x578px\|Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)\|alt=\|center]]

Gs726: Added Yangon Area application.

2021-12-15T22:44:18Z

Added Yangon Area application.

← Older revision		Revision as of 18:44, 15 December 2021
Line 156:		Line 156:

	Optimal routes are essential in creating successful transportation systems. Transportation systems affect entire societies and their quality of life. Minimizing transportation time and distance, effectively reduces time spent traveling, traffic, risk of death or injury while traveling, air pollution and costs incurred from traveling. Transportation is also considered a barrier to impoverished communities, affecting access to employment and other essential services, directly impacting economies. The objective of applying the A* algorithm to transportation challenges is to minimize cost and travel time for transportation.		Optimal routes are essential in creating successful transportation systems. Transportation systems affect entire societies and their quality of life. Minimizing transportation time and distance, effectively reduces time spent traveling, traffic, risk of death or injury while traveling, air pollution and costs incurred from traveling. Transportation is also considered a barrier to impoverished communities, affecting access to employment and other essential services, directly impacting economies. The objective of applying the A* algorithm to transportation challenges is to minimize cost and travel time for transportation.


			An analysis was conducted on the transportation system in Yangon, Myanmar. Public transportation in the Yangon area is prevalent and the preferred method of transportation is public transportation. In this study, the bus routes were utilized to construct the algorithm to determine shortest paths in their transportation network. Bus stops were represented through nodes and bus lines were the links between those nodes.

			[[File:Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint).png\|left\|thumb\|578x578px\|Sample Data Yangon Area (Zar, Myat Thu and Sein, Myint Myint)]]


			The approach to analysis with the implementation of the A* algorithm was similar to our initial approach. This proposed system in the Yangon area focused solely on the distance between nodes. To improve efficiency, an algorithm that includes data and analysis on traffic patterns, road closures and wait times for bus stops would aid users in optimizing their transportation selection. The use of the A* algorithm bus network in a region so heavily reliant on public transportation is a respectable strategy to address transportation concerns in the Yangon area.

	'''Pathfinding in Video Games'''		'''Pathfinding in Video Games'''

	Pathfinding algorithms are increasingly used in video game development globally. Artificial Intelligence issues are prevalent as these games increase in complexity. Decision-making, movements and strategy are instances where pathfinding algorithms, such as the A* algorithm, are utilized to find optimal solutions. In video games where users make decisions, path finding may increase with complexity as decisions are dynamic according to the user's input. Pathfinding uses up CPU power and memory. The objective is to optimize paths between characters and their endpoints to minimize CPU power and memory used to maximize game performance.		Pathfinding algorithms are increasingly used in video game development globally. Artificial Intelligence issues are prevalent as these games increase in complexity. Decision-making, movements and strategy are instances where pathfinding algorithms, such as the A* algorithm, are utilized to find optimal solutions. In video games where users make decisions, path finding may increase with complexity as decisions are dynamic according to the user's input. Pathfinding uses up CPU power and memory. The objective is to optimize paths between characters and their endpoints to minimize CPU power and memory used to maximize game performance.


	== Conclusion ==		== Conclusion ==