{"id":29,"date":"2009-03-06T01:20:20","date_gmt":"2009-03-06T06:20:20","guid":{"rendered":"http:\/\/jamesdevine.info\/?page_id=29"},"modified":"2021-12-23T18:47:53","modified_gmt":"2021-12-23T23:47:53","slug":"a-solution-to-the-traffic-jam-game","status":"publish","type":"page","link":"https:\/\/jamesdevine.info\/index.php\/projects\/a-solution-to-the-traffic-jam-game\/","title":{"rendered":"A* Solution to the Traffic Jam Game"},"content":{"rendered":"<h3><a href=\"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2009\/03\/traffic_jam.jpg?ssl=1\"><img data-recalc-dims=\"1\" decoding=\"async\" class=\"aligncenter size-full wp-image-38\" title=\"traffic_jam\" src=\"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2009\/03\/traffic_jam.jpg?resize=83%2C83&#038;ssl=1\" alt=\"traffic_jam\" width=\"83\" height=\"83\" \/><\/a><\/h3>\n<h3>About A*<\/h3>\n<p>The A* search algorithm is a search algorithm that uses a heuristic to estimate the cost of taking a given path in the solution tree to the goal state. The cost is calculated by adding the g + h values. The g value is the cost in steps to get to the current state and the h value is the estimated distance from the solution. For the algorithm to work correctly the heuristic must be at best an underestimate of the actual distance from a solution.<\/p>\n<h3>How the Code Works<\/h3>\n<p>The actual A* search is only a few lines of code. It first takes a board node from the top of the priority queue, if the node is a goal node the algorithm quits, if not it expands all of the board conconfigurations that are reachable from the current board node and adds then to the queue(after checking to make sure that the board node has not been explored). The process is repeated until the queue is emptied or a solution is found. In the event that the queue is emptied it signals that there is no solution.<br \/>\nThe implementation used generates board configurations and then adds then to board nodes. Each board has the ability to calculate its heuristic, generate all moves that can be made, generate a hash, and determine if the board is at a goal state. To determine if a board is at a goal state the method isGoal checks to make sure there are spaces before the car trying to exit and the exit. The heuristic is determined by adding the number of spaces that are blocked in front of the car trying to exit.<\/p>\n<p>The driver program can take an integer command line argument from 1-10 that will use a stored board to solve. The boards range in complexity, with numbers closer to 10 being harder to solve. All of the boards are solvable though.<\/p>\n<h3>Source Code<\/h3>\n<p>The source code for the program can be downloaded here: <a href=\"https:\/\/jamesdevine.info\/wp-content\/uploads\/2009\/03\/rushhour.tar\">Rush Hour Code<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>About A* The A* search algorithm is a search algorithm that uses a heuristic to estimate the cost of taking [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"class_list":["post-29","page","type-page","status-publish","hentry"],"aioseo_notices":[],"jetpack-related-posts":[{"id":186,"url":"https:\/\/jamesdevine.info\/index.php\/projects\/cuda-parallel-merge-sort\/","url_meta":{"origin":29,"position":0},"title":"CUDA Parallel Merge Sort","author":"James Devine","date":"May 3, 2009","format":false,"excerpt":"This work was part of a final project for Programming Languages. The CUDA API was investigated and used to write a parallel merge sort algorithm that executes on the Graphics Processing Unit(GPU), through a technique called GPGPU. GPGPU stand for General Purpose computing on a GPU. GPGPU allows for the\u2026","rel":"","context":"In &quot;General&quot;","block_context":{"text":"General","link":"https:\/\/jamesdevine.info\/index.php\/category\/general-information\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":5,"url":"https:\/\/jamesdevine.info\/index.php\/projects\/","url_meta":{"origin":29,"position":1},"title":"Archive","author":"James Devine","date":"March 5, 2009","format":false,"excerpt":"This page highlights some old projects I've worked on","rel":"","context":"In &quot;General&quot;","block_context":{"text":"General","link":"https:\/\/jamesdevine.info\/index.php\/category\/general-information\/"},"img":{"alt_text":"xen","src":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2009\/03\/xen.jpeg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":88490,"url":"https:\/\/jamesdevine.info\/index.php\/pages\/about-tidy\/","url_meta":{"origin":29,"position":2},"title":"About Tidy","author":"James Devine","date":"March 18, 2021","format":false,"excerpt":"[vc_row row_height_percent=\"0\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"7\" bottom_padding=\"7\" back_color=\"color-xsdn\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\"][vc_column column_width_use_pixel=\"yes\" align_horizontal=\"align_center\" gutter_size=\"3\" overlay_alpha=\"50\" shift_x=\"0\" shift_y=\"0\" shift_y_down=\"0\" z_index=\"0\" medium_width=\"0\" mobile_width=\"0\" width=\"1\/1\" column_width_pixel=\"900\"][vc_custom_heading heading_semantic=\"h1\" text_font=\"font-136269\" text_size=\"fontsize-338686\" text_weight=\"500\" uncode_shortcode_id=\"178330\"]We are a brand and design studio[\/vc_custom_heading][\/vc_column][\/vc_row][vc_row row_height_percent=\"0\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"0\" bottom_padding=\"5\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\"][vc_column column_width_percent=\"100\" gutter_size=\"3\" style=\"dark\" overlay_alpha=\"50\" shift_x=\"0\"\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-2-min.jpg?fit=1200%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-2-min.jpg?fit=1200%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-2-min.jpg?fit=1200%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-2-min.jpg?fit=1200%2C800&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-2-min.jpg?fit=1200%2C800&ssl=1&resize=1050%2C600 3x"},"classes":[]},{"id":88776,"url":"https:\/\/jamesdevine.info\/index.php\/pages\/about-wide\/","url_meta":{"origin":29,"position":3},"title":"About Wide","author":"James Devine","date":"March 19, 2021","format":false,"excerpt":"[vc_row row_height_percent=\"75\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"7\" bottom_padding=\"7\" back_color=\"color-xsdn\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\"][vc_column column_width_use_pixel=\"yes\" position_vertical=\"middle\" align_horizontal=\"align_center\" gutter_size=\"2\" overlay_alpha=\"50\" shift_x=\"0\" shift_y=\"0\" shift_y_down=\"0\" z_index=\"0\" medium_width=\"0\" mobile_width=\"0\" width=\"1\/1\" column_width_pixel=\"1000\"][vc_custom_heading text_color=\"color-210407\" heading_semantic=\"h6\" text_font=\"font-103074\" text_size=\"fontsize-160000\" text_weight=\"600\" text_transform=\"uppercase\" text_space=\"fontspace-210350\"]Shaping business[\/vc_custom_heading][vc_custom_heading heading_semantic=\"h1\" text_font=\"font-175345\" text_size=\"fontsize-338686\" text_weight=\"400\"]The secret of success is working with talents[\/vc_custom_heading][vc_empty_space][vc_button button_color=\"color-210407\" radius=\"btn-circle\" text_skin=\"yes\" custom_typo=\"yes\" font_family=\"font-175345\" font_weight=\"400\"\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":57560,"url":"https:\/\/jamesdevine.info\/index.php\/creative-corporation\/","url_meta":{"origin":29,"position":4},"title":"Creative Corporation","author":"James Devine","date":"May 9, 2017","format":false,"excerpt":"[vc_row row_height_percent=\"85\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"5\" bottom_padding=\"5\" back_color=\"color-wayh\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\" front_end_with_slider=\"true\" uncode_shortcode_id=\"916641\" back_color_type=\"uncode-palette\"][vc_column column_width_percent=\"100\" position_vertical=\"bottom\" gutter_size=\"3\" style=\"dark\" overlay_alpha=\"50\" shift_x=\"0\" shift_y=\"0\" shift_y_down=\"0\" z_index=\"0\" medium_width=\"0\" mobile_width=\"0\" zoom_width=\"0\" zoom_height=\"0\" width=\"1\/1\"][uncode_slider slider_interval=\"5000\" slider_navspeed=\"400\" slider_loop=\"yes\" slider_hide_arrows=\"yes\" slider_dot_position=\"left\" slider_dot_width=\"limit\" slider_width_percent=\"100\" h_padding=\"2\" slider_dot_align=\"left\"][vc_row_inner row_inner_height_percent=\"0\" back_color=\"color-wayh\" back_image=\"11309\" back_position=\"center bottom\" parallax=\"yes\" kburns=\"yes\" overlay_color=\"color-wayh\" overlay_alpha=\"20\" gutter_size=\"4\" shift_y=\"0\" z_index=\"0\"\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/demo-homepage-Creative-Corporation-Uncode.jpg?fit=1200%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/demo-homepage-Creative-Corporation-Uncode.jpg?fit=1200%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/demo-homepage-Creative-Corporation-Uncode.jpg?fit=1200%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/demo-homepage-Creative-Corporation-Uncode.jpg?fit=1200%2C800&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/demo-homepage-Creative-Corporation-Uncode.jpg?fit=1200%2C800&ssl=1&resize=1050%2C600 3x"},"classes":[]},{"id":88491,"url":"https:\/\/jamesdevine.info\/index.php\/pages\/services-tidy\/","url_meta":{"origin":29,"position":5},"title":"Services Tidy","author":"James Devine","date":"March 18, 2021","format":false,"excerpt":"[vc_row row_height_percent=\"0\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"7\" bottom_padding=\"7\" back_color=\"color-xsdn\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\"][vc_column column_width_use_pixel=\"yes\" align_horizontal=\"align_center\" gutter_size=\"3\" overlay_alpha=\"50\" shift_x=\"0\" shift_y=\"0\" shift_y_down=\"0\" z_index=\"0\" medium_width=\"0\" mobile_width=\"0\" width=\"1\/1\" column_width_pixel=\"900\"][vc_custom_heading heading_semantic=\"h1\" text_font=\"font-136269\" text_size=\"fontsize-338686\" text_weight=\"500\" uncode_shortcode_id=\"305920\"]We provide digital and media services[\/vc_custom_heading][\/vc_column][\/vc_row][vc_row row_height_percent=\"0\" override_padding=\"yes\" h_padding=\"2\" top_padding=\"0\" bottom_padding=\"5\" overlay_alpha=\"50\" gutter_size=\"3\" column_width_percent=\"100\" shift_y=\"0\" z_index=\"0\"][vc_column column_width_percent=\"100\" gutter_size=\"3\" style=\"dark\" overlay_alpha=\"50\" shift_x=\"0\" shift_y=\"0\"\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-10-min.jpg?fit=1200%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-10-min.jpg?fit=1200%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-10-min.jpg?fit=1200%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-10-min.jpg?fit=1200%2C800&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/jamesdevine.info\/wp-content\/uploads\/2021\/10\/image-placeholder-10-min.jpg?fit=1200%2C800&ssl=1&resize=1050%2C600 3x"},"classes":[]}],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/pages\/29","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/comments?post=29"}],"version-history":[{"count":17,"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/pages\/29\/revisions"}],"predecessor-version":[{"id":103245,"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/pages\/29\/revisions\/103245"}],"up":[{"embeddable":true,"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/pages\/5"}],"wp:attachment":[{"href":"https:\/\/jamesdevine.info\/index.php\/wp-json\/wp\/v2\/media?parent=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}