How to model following map for AI wayfinding? - Developers

[IMG]http://i61.tinypic.com/27bf6.png[/IMG] So I need to program AI that calculates best paths to take to reach the destination from given starting point. I need to model given map in a suitable representation as a search problem. I will have to make estimations for distances. Any suggestions how should I go about digitizing given map for functionality when programming?

A* algorithm can be used for this, and you can give "penalty" to nodes, so the roads have the least penalty and grass highest penalty. Why penalty? So AI will prefer roads to walk on. About digitizing such map, It is complex but it is doable. You need to read on graph theory [url]http://en.wikipedia.org/wiki/Graph_theory[/url]. Non-optimal solution would be to just convert whole image into 2D graph. Moderns CPUs can handle this stuff easily, but it is quite non optimized way. The more optimal solution would be to lower the images resolution, then convert it to 2D graph. Even more optimal solutions exist, like grouping nodes with same 'color' and then creating bigger nodes. Is this school homework? Just wondering.

If you need a A* tutorial I recommend reading this one: [url]http://www.policyalmanac.org/games/aStarTutorial.htm[/url]

[QUOTE=AntonioR;46081121]If you need a A* tutorial I recommend reading this one: [url]http://www.policyalmanac.org/games/aStarTutorial.htm[/url][/QUOTE] I used this tutorial and recommended it as well.

Is there any other way of modeling the map other than 2D graph? Could it be represented in text?

A* can also work with a coordinate system, just make sure the lengths between the coordinates are correctly calculated. I'm assuming that's what you mean when you want to represent it in text.

[quote] Submission Type: An archive file including the softcopy report and the source codes to be submitted using x. Consider an autonomous agent that carries packages from a starting point to a given destination in Campus whose map is given on the right. In this question, you are required to model this problem as a search problem and implement the search algorithms to find the most suitable route for the given start and end points. a) (10 pts) Model the given map in a suitable representation as a search problem. You can make estimations for the distances. b) (20 pts) Run tree search versions of BFS and DFS to find a route from 2 to 11 and compare the results. Report your findings. c) (20 pts) Devise two heuristic functions to use with the graph search version of the A* algorithm and show that they are both admissible and consistent. d) (20 pts) Run the graph search version of A* to find a route from 2 to 11 by using the two heuristics you determined in (c) separately, analyze and compare the results. Report your findings. e) (15 pts) Discuss what you should do either in representation or in the search algorithms so that the user can give certain places to be visited on the route. For example, finding a route from 2 to 11 by visiting 8. f) (15 pts) Discuss what you should do either in representation or in the search algorithms so that the user can give certain paths to be passed on the route. For example, finding a route from 2 to 11 by passing from the road b. For this homework, you can use existing BFS, DFS or A* algorithm implementations such as the ones provided for “Artificial Intelligence: A Modern Approach” book: [url]http://aima.cs.berkeley.edu/code.html[/url] [/quote] This is the whole assignment. I have to submit it by October 10. Any pointers where I should start? Can someone give me some pointers please? I feel stuck. If I know how to tap into it, then I would. I don't have any problems with programming if given problem is clearly defined. I would really appreciate it if someone could define how should I go about it. Converting map to 2D graph sounds complex and I don't know how I would go about implementing coordinate system and making roads and points known on it. [editline]29th September 2014[/editline] [QUOTE=FalconKrunch;46088099]A* can also work with a coordinate system, just make sure the lengths between the coordinates are correctly calculated. I'm assuming that's what you mean when you want to represent it in text.[/QUOTE] I was thinking more of like making list of connections. Giving name for each road and then defining which ones connect and how much it costs distance-wise to travel given connection.

[QUOTE=HJ23;46103847] Converting map to 2D graph sounds complex and I don't know how I would go about implementing coordinate system and making roads and points known on it. [/QUOTE] Make some struct/class for node you like and enum. [code] enum Type { Road, Grass, Wall, } struct Node { bool visited; Type type; } [/code] Then just make 2D array. You don't need to references from nodes to each other because you already know they are arranged into a grid. I hope you can read this pseudocode: [code] Image image = //import your image here, it is 2D array of RGB(A) values int width = image.width; int height = image.height; Node[][] graph = new Node[width][height]; //read image data for(var x = 0; x < width; x++) for(var y = 0; y < height; y++){ //and so on if(image[x][y].rgb == Color.roadColor) { graph.type == Type.Road; } else //... } [/code] Now with your algorithm you can just 'crawl' from starting point to end. [editline]29th September 2014[/editline] [QUOTE=HJ23;46103847] I was thinking more of like making list of connections. Giving name for each road and then defining which ones connect and how much it costs distance-wise to travel given connection.[/QUOTE] Ok this problem is a bit more problematic, but it is doable. First extract road pixels and then perform some stuff on them. I don't know exactly.

[QUOTE=Fourier;46103935]Ok this problem is a bit more problematic, but it is doable. First extract road pixels and then perform some stuff on them. I don't know exactly.[/QUOTE] This sounds overly complex. Looking over the assignment requirements it never states that the coordinates need to be assigned by an algorithm. I'm assuming he can just use XML or something where he can easily input coordinates and their neighbors. [QUOTE=HJ23;46103847]I was thinking more of like making list of connections. Giving name for each road and then defining which ones connect and how much it costs distance-wise to travel given connection.[/QUOTE] I'd suggest calculating the cost during the algorithm, so that if you change or add a point you don't have to edit all related costs in the file again.

How do I go about importing image as 2D array of RGB colors in Python? Should I use Python for this assignment?

[QUOTE=HJ23;46113091]How do I go about importing image as 2D array of RGB colors in Python? Should I use Python for this assignment?[/QUOTE] It [I]probably[/I] doesn't matter, so whatever you're best at. Is there a limit on how long it's allowed to work towards the answer?

I wouldn't be in your skin, that homework is not simple. Btw, some of you over complicate things. Map can be a set of nodes with x, y values and id (and those g,h,f for A*) . Each node also has ids of nodes that are connected to it. Those can be just a set of id numbers, or better, a link struct which doesn't hold just an id of the neighbor, but the cost to get there (cost can be just the distance between two nodes multiplied by some factor(grass, concrete, stairs...)). I have recently made this for pathfinding in my engine: [img]http://i.imgur.com/t2XGSBa.png[/img] This is how I store it in xml (n=x y id, c stores ids of nodes that are connected to it. First you create all the nodes, then using the ids you create links/connections. In the end this forms a tree structure and you use A* to run trough it to build paths. Recursion is a bitch btw. [code] <Tree> <Node n="481 358 0" c="1 16 25 " /> <Node n="578 358 1" c="0 2 3 " /> <Node n="579 377 2" c="1 " /> <Node n="599 355 3" c="1 4 30 " /> <Node n="633 356 4" c="3 5 6 " /> <Node n="633 374 5" c="4 " /> <Node n="687 355 6" c="4 7 8 " /> <Node n="688 373 7" c="6 " /> <Node n="731 354 8" c="6 9 18 " /> . . . <Tree> [/code]