Intelligent Rogue Chars
Intelligent game-playing characters have been used in the game industry to harness the power of graph algorithms to navigate complex virtual environments, strategically analyzing interconnected nodes and edges to optimize their movements and decision- making processes. By leveraging graph traversal techniques such as breadth-first search (BFS) and depth-first search (DFS), these characters can efficiently explore vast game worlds, identify optimal paths, and anticipate opponent movements.
Develop an effective approach to track and intercept a moving opponent in a (simplified version of the) 2D Game called Rogue. You will also create a viable plan to evade interception from said opponent.
Rules of the Game
The game of Rogue is played on an N-by-N grid that represents the dungeon. The two players are a rogue and a monster. The rogue is represented with the character @. The monster is represented by an uppercase letter A through Z.
The monster and rogue take turns making moves, with the monster going first. If the monster intercepts the rogue (i.e., occupies the same site), then the monster kills the rogue, and the game ends. In each turn, a player either remains stationary or moves to an adjacent site.
There are three types of sites:
1. Rooms represented by .
2. Corridors represented by +
3. Walls represented by (a space)
The movement rules are:
. If a player is in a room site, then they can move to an adjacent room site in one of the 8 compass directions (N, E, S, W, NW, NE, SW, SE) or a corridor site in one of the 4 directions (N, E,S, W).
. If a player is in a corridor site, then they can move to an adjacent room or corridor site in one of the 4 directions (N, E,S, W).
. The walls are impenetrable.
Consider the following two dungeons.
In the first dungeon above, the rogue can avoid the monster I indefinitely by moving N and running around the corridor.
In the second dungeon, the monster A can use the diagonal moves to trap the rogue in a corner.
Monster's Strategy
The monster is tenacious and its sole mission is to chase and intercept the rogue. A natural strategy for the monster is to always take one step toward the rogue. In terms of the underlying graph, this means that the monster should compute a shortest path between itself and the rogue, and take one step along such a path. This strategy is not necessarily optimal, since there maybe ties, and taking a step along one shortest path may be better than taking a step along another shortest path.
Consider the following two dungeons.
In the first dungeon above, monster B's only optimal strategy is to take a step in the NE direction. Moving N or E would enable the rogue to make a mad dash for the opposite corridor entrance.
In the second dungeon, the monster C can guarantee to intercept the rogue by first moving E.
Your first task is to implement an effective strategy for the monster. To implement the monster's strategy, you may want to consider using BFS.
Rogue's Strategy
The rogue's goal is to avoid the monster for as long as possible. A naive strategy is to move to an adjacent site that is as far as possible from the monster's current location.
That strategy is not necessarily optimal.
Consider the following two dungeons.
It is easy to see that that strategy may lead to a quick and unnecessary death, as in the second dungeon above where the rogue can avoid the monster J by moving SE.
Another potentially deadly strategy would be togo to the nearest corridor. To avoid the monster F in the first dungeon, the rogue must move towards a northern corridor instead.
A more effective strategy is to identify a sequence of adjacent corridor and room sites which the rogue can run around in circles forever, thereby avoiding the monster indefinitely. This involves identifying and following certain cycles in the underlying graph. Of course, such cycles may not always exist, in which case your goal is to survive for as long as possible. To implement the rogue's strategy, you may want to use both BFS and DFS.
Implementation and Specification
In this section, you will discover the expected details regarding the implementation and specifications of the Rogue game, which you are required to adhere to.
Dungeon File Input Format
The input dungeon consists of an integer N, followed by N rows of 2N characters each. For example:
A room is a contiguous rectangular block of room sites. Rooms may not connect directly with each other. That is, any path from one room to another will use at least one corridor site.
There will be exactly one monster and one rogue, and each will start in some room site.
You will be given 18 dungeon files to test your code with.
You may create your own dungeon files (explain the novelty in your report/video!). In the rubric subsection below, you are required to show the correctness and the performance of your rogue and monster on at least 5 non-trivial dungeons in total.
Game of Rogue Specification
We will provide some files that are already completed as the game infrastructure. There are two files to complete: Monster.java and Rogue.java, for which some skeleton code is provided.
The given files are only for a quick start: you should modify the files so your program exhibits more object-oriented programming principles!
The following is the interface of Monster.java :
public Monster(Game g) // create a new monster playing game g
public Site move() // return adjacent site to which it moves
And the analogous program Rogue.java:
public Rogue(Game g) // create a new rogue playing a game g
public Site move() // return adjacent site to which it moves
The move() method should implement the move of the monster/rogue as specified by the strategy that you have created.
Game.java reads in the dungeon from standard input and does the game playing and refereeing. It has three primary interface functions that will be needed by
Rogue.java and Monster.java. public Site getMonsterSite() public Site getRogueSite()
public Dungeon getDungeon()
// return site occupied by monster // return site occupied by rogue
// return the dungeon
Dungeon.java represents an N-by-N dungeon.
public boolean isLegalMove(Site v, Site w) // is moving from site v
to w legal?
public boolean isCorridor(Site v) // is site v a corridor site?
public boolean isRoom(Site v) // is site v a room site?
public int size() // return N = dim of dungeon
In.java is a library from Algorithms optional textbook to read in data from various sources. You will have to create your own input library for your CW3 program.
Site.java is a data type that represents a location site in the N-by-N dungeon.
public Site(int i, int j) // create new Site for location (i, j)
public int i() // get i coordinate
public int j() // get j coordinate
public int manhattan(Site w) // return Manhattan distance
from invoking site to w
public boolean equals(Site w) // is invoking site equal to w?
If you have two sites located at coordinates (i1, j1) and (i2, j2), then the Manhattan distance between the two sites is |i1 - i2 | + |j1 - j2 |. This represents the length you have to travel, assuming you can only move horizontally and vertically.
You should modify the files or create other Java files, so your final program exhibits more object-oriented programming principles. Finally, you must only use libraries that are covered in CPT204 (including in Liang textbook). Violating this by using libraries that are not covered in CPT204 will result in an automatic total mark of 0.
Deliverables
In this section, you will find the details regarding the files that you are required to submit,and the report and video specifications.
Submission Requirements
You are required to submit:
1) The Rogue.java and Monster.java source code Java files, as well as any other auxiliary Java files and the dungeon files that you selected/created in your project, altogether combined in a ZIP file.
2) Your report, in both Word and PDF format (2 separate files).
请加QQ:99515681 邮箱:99515681@qq.com WX:codinghelp
- 赛诺威盛:大孔径专科化CT领航者
- 网易硬刚腾讯 两大游戏玩家之间的口水仗不断
- 全球“最独特”的一台华为 nova 6 5G 版手机是什么样子的?
- 拼多多抖音淘宝京东,谁是真低价?
- 老杨第一次再度抓握住一瓶水,他由此产生了新的憧憬
- 丰田章男称未来依然需要内燃机 已经启动电动机新项目
- B站更新决策机构名单:共有 29 名掌权管理者,包括陈睿、徐逸、李旎、樊欣等人
- 苹果罕见大降价,华为的压力给到了?
- 三明列东又有房子要拆迁!住这里的人要发了!
- 放大招后,广州又忍不住了…
- 私募积极加仓,百亿股票私募仓位指数创出近八周新高
- 他,传闻中马云最想见的人
- 升级的脉脉,正在以招聘业务铺开商业化版图
- 如何经营一家好企业,需要具备什么要素特点
- 智慧驱动 共创未来| 东芝硬盘创新数据存储技术