• 05-12-2013
Tobias Mihel
So I got a task from our countries programming team to do this but I have no idea how I could go at it (I'm not looking for a solution in code but just how I could be able to do this in C++)

So you have a square chess field which is N x N fields big (get as input) and you have a rook placed on X1 and Y1 coords. You need to get it to X2 Y2 coords and calculate the cost of the cheapest way (if no way possible output is -1) with the costs of Cx (cost of moving 1 square in x-axis) and Cy (cost of moving 1 square in y-axis) then you get an input for M which is amount of obstacles. Followed by M lines of Xi Yi coords of the obstacles. You have to find the cheapest way from X1 Y1 to X2 Y2. The rook can only move left/right up/down and can't jump over obstacles.

Any help would be appreciated. The only problem I am having is how to count the obstacles in the equation.
• 05-12-2013
rogster001
Quote:

So you have a square chess field which is N x N fields big (get as input)
why on earth would you be required to input the size of a chess board? Unless there are variations involved?

Quote:

The rook can only move left/right up/down and can't jump over obstacles.
again, that is implicit in the game. Do you just need a move evaluation or is there a set problem like say knights tour to code? Are there any other pieces involved in this problem?

Show your work - dont post the entire thing if it is not relevant, start with just the function / construct you are having difficulties with
• 05-12-2013
Tobias Mihel
There are variations involved. I know how I would calculate without the obstacles but I don't know how to take the obstacles into the equation or try another path. I just need a general idea how to do it not in code.
• 05-12-2013
Cat
Hmm, just a quick thought, but what about an algorithm like this (whether or not this is efficient depends on exactly what you need to do with it - if you were going to do multiple trials with the same obstacles and end points it could actually be the most efficient):

* Create an array equal to the board size to store the minimum distance from each point to the target point.
* Initialize these all to a sentinel value (a very large number - greater than any possible calculated distance)
* Initialize the locations of the obstacles to another sentinel value (e.g. -1)
* Create a queue to store locations that you need to process.
* Start the algorithm by processing the X2 Y2 location (cost here is 0), and enqueue the four adjacent squares (unless they are out of bounds or obstacles).

* While the queue is not empty, do the following:
1. Remove the location from the queue
2. Check this location against its four adjacent squares (unless out of bounds/obstacles) to determine what the minimal distance is from this new square. Save this minimum calculated amount.
3. If any adjacent locations have minimal distances that are greater than this location's minimum distance plus the cost of moving from that square to this one, queue that location for recalculation. (This should automatically catch any squares that haven't yet been calculated since those have very large distances). You can optimize this by making sure no location is currently in the queue more than once.

* When the queue is empty, any remaining unprocessed squares have no path to the target location.

Essentially, the third step of the loop recalculates distances if a shorter path was found later (because the original calculation was made before all adjacent squares were calculated, this will sometimes happen).
• 05-12-2013
Elysia
That's rather advanced for a first look at the problem.
Here is a list of suggestions:
- At (x, y), for every possible move check:
-- Can the piece move there from (x, y)?
-- Is there an obstacle in the way?
- If no to both questions, move the piece, document the cost and repeat recursively.
- If yes to at least one question, fail and backtrack.

How to implement this is up to you.
Try tackling each problem in part, then piecing it together. For example, make a function that checks if a piece can move to (x2, y2) from (x1, y1).
This is a well known backtracking way of handling it.
• 05-12-2013
iMalc
Some people may have over-thought this one. It's no different whether there is barely a single obstacle on the board, or the board is almost entirely filled.

This is a simple optimal-pathfinding problem, to which the A* algorithm is perfectly suited. I would not consider any other approach.
• 05-13-2013
Elysia
If you know graph theory, sure. If you don't have dijkstra at hand, though, it may be a little more difficult.
• 05-13-2013
rogster001
iMalc identified that well, A* is not that hard and is a great programming project.
• 05-13-2013
Cat
Quote:

Originally Posted by iMalc
Some people may have over-thought this one. It's no different whether there is barely a single obstacle on the board, or the board is almost entirely filled.

This is a simple optimal-pathfinding problem, to which the A* algorithm is perfectly suited. I would not consider any other approach.

Hmm, I hadn't come across that algorithm before - thanks for sharing that! One more algorithm to file away for future reference :)